## 190 - Circle Through Three Points

**Moderator:** Board moderators

- Moni
- Experienced poster
**Posts:**202**Joined:**Fri Mar 22, 2002 2:00 am**Location:**Chittagong. CSE - CUET-
**Contact:**

Oh! Again that 190..........

Why don't you read :

http://acm.uva.es/board/viewtopic.php?t=2515

( Lot of efforts )

Hmm... The Pic... Is also there !!!

Why don't you read :

http://acm.uva.es/board/viewtopic.php?t=2515

( Lot of efforts )

Hmm... The Pic... Is also there !!!

*We are all in a circular way, no advances, only moving and moving!*### problem 190

How can i now how many input lines there are, my program gives correct solution but i dont know when the input ends[/c]

### 190

This is my solution of 190 Circle-Three points and works fine on my Visual C++ compiler, but im not sure when the input ends . So i am doing while loop ( while(gets(string)) ) but i am getting wrong answer. Can anyone help me ?

#include <stdio.h>

#include <malloc.h>

#include <math.h>

#include <string.h>

struct krug

{

float k;

float h;

float r;

float kc;

float kd;

float ke;

struct krug *next;

};

typedef struct krug cvor;

void push(cvor element,cvor **glava); /* Radimo sa "listom" */

int main()

{

cvor *glava,krug1,*p;

char string[200];

float x1,y1,x2,y2,x3,y3,h,k,kc,kd,ke;

float a,b,c,d,r;

char c1,c2,pc,pd,pe;

int counter=0;

glava=NULL;

p=NULL;

while(gets(string))

{

if(strlen(string)==0)

break;

else

{ sscanf(&string[0],"%f %f %f %f %f %f",&x1,&y1,&x2,&y2,&x3,&y3);

counter++;

a=2*(y1-y2)/(x2-x1)*(x3-x1)+2*(y3-y1);

b=((float)pow(x3,2)-(float)pow(x1,2))+((float)pow(y1,2)-(float)pow(y2,2) +(float)pow(x1,2)-(float)pow(x2,2))/(x2-x1)*(x3-x1)+((float)pow(y3,2)-(float)pow(y1,2));

k=b/a;

c=2*k*(y1-y2)+((float)pow(y2,2)-(float)pow(y1,2))+((float)pow(x2,2)-(float)pow(x1,2));

d=2*(x2-x1);

h=c/d;

r=(float)pow((float)pow(x1-h,2)+(float)pow(y1-k,2),0.5);

kc=-2*h; kd=-2*k; ke=h*h + k*k -r*r;

krug1.k=k;

krug1.h=h;

krug1.r=r;

krug1.kc=kc;

krug1.kd=kd;

krug1.ke=ke;

krug1.next=NULL;

push(krug1,&glava);

}

};

counter=0;

for (p = glava; p != NULL; p = p->next)

{

counter++;

if(counter>2)

break;

krug1=*p;

counter--;

k=krug1.k;

h=krug1.h;

r=krug1.r;

kc=krug1.kc;

kd=krug1.kd;

ke=krug1.ke;

if(h>=0)

c1='-';

else

c1='+';

if(k>=0)

c2='-';

else

c2='+';

if(kc>=0)

pc='+';

else

pc='-';

if(kd>=0)

pd='+';

else

pd='-';

if(ke>=0)

pe='+';

else

pe='-';

printf("\n(x %c %.3f)^2 + (y %c %.3f)^2 = %.3f^2",c1,fabs(h),c2,fabs(k),r);

printf("\nx^2 + y^2 %c %.3fx %c %.3fy %c %.3f = 0\n",pc,fabs(kc),pd,fabs(kd),pe,fabs(ke));

}

return 0;

}

void push(cvor element,cvor **glava)

{

cvor *novi,*p;

p=NULL;

novi=(cvor *)malloc(sizeof(cvor));

novi->h=element.h;

novi->k=element.k;

novi->r=element.r;

novi->kc=element.kc;

novi->kd=element.kd;

novi->ke=element.ke;

if (*glava == NULL)

{

novi->next=*glava;

*glava=novi;

}

else

{

for(p=*glava;p->next;p=p->next);

novi->next = p->next;

p->next = novi;

}

}

#include <stdio.h>

#include <malloc.h>

#include <math.h>

#include <string.h>

struct krug

{

float k;

float h;

float r;

float kc;

float kd;

float ke;

struct krug *next;

};

typedef struct krug cvor;

void push(cvor element,cvor **glava); /* Radimo sa "listom" */

int main()

{

cvor *glava,krug1,*p;

char string[200];

float x1,y1,x2,y2,x3,y3,h,k,kc,kd,ke;

float a,b,c,d,r;

char c1,c2,pc,pd,pe;

int counter=0;

glava=NULL;

p=NULL;

while(gets(string))

{

if(strlen(string)==0)

break;

else

{ sscanf(&string[0],"%f %f %f %f %f %f",&x1,&y1,&x2,&y2,&x3,&y3);

counter++;

a=2*(y1-y2)/(x2-x1)*(x3-x1)+2*(y3-y1);

b=((float)pow(x3,2)-(float)pow(x1,2))+((float)pow(y1,2)-(float)pow(y2,2) +(float)pow(x1,2)-(float)pow(x2,2))/(x2-x1)*(x3-x1)+((float)pow(y3,2)-(float)pow(y1,2));

k=b/a;

c=2*k*(y1-y2)+((float)pow(y2,2)-(float)pow(y1,2))+((float)pow(x2,2)-(float)pow(x1,2));

d=2*(x2-x1);

h=c/d;

r=(float)pow((float)pow(x1-h,2)+(float)pow(y1-k,2),0.5);

kc=-2*h; kd=-2*k; ke=h*h + k*k -r*r;

krug1.k=k;

krug1.h=h;

krug1.r=r;

krug1.kc=kc;

krug1.kd=kd;

krug1.ke=ke;

krug1.next=NULL;

push(krug1,&glava);

}

};

counter=0;

for (p = glava; p != NULL; p = p->next)

{

counter++;

if(counter>2)

break;

krug1=*p;

counter--;

k=krug1.k;

h=krug1.h;

r=krug1.r;

kc=krug1.kc;

kd=krug1.kd;

ke=krug1.ke;

if(h>=0)

c1='-';

else

c1='+';

if(k>=0)

c2='-';

else

c2='+';

if(kc>=0)

pc='+';

else

pc='-';

if(kd>=0)

pd='+';

else

pd='-';

if(ke>=0)

pe='+';

else

pe='-';

printf("\n(x %c %.3f)^2 + (y %c %.3f)^2 = %.3f^2",c1,fabs(h),c2,fabs(k),r);

printf("\nx^2 + y^2 %c %.3fx %c %.3fy %c %.3f = 0\n",pc,fabs(kc),pd,fabs(kd),pe,fabs(ke));

}

return 0;

}

void push(cvor element,cvor **glava)

{

cvor *novi,*p;

p=NULL;

novi=(cvor *)malloc(sizeof(cvor));

novi->h=element.h;

novi->k=element.k;

novi->r=element.r;

novi->kc=element.kc;

novi->kd=element.kd;

novi->ke=element.ke;

if (*glava == NULL)

{

novi->next=*glava;

*glava=novi;

}

else

{

for(p=*glava;p->next;p=p->next);

novi->next = p->next;

p->next = novi;

}

}

### WA in 190 using Pascal

well, got a problem. My program works fine for every input it came on my mind (circle is on P = 0 , Q = 0 , r = 0 , ...) but it still doesn't works fine (according to judge:). In problem there is no specific description on how cases such p=0 or q=0 or (r=0 - then it is a point) shgould be handled. Should it be like this ?

(x - 0.000)^2 + ....

or like this ?

x^2 + ....

Thanks.

(x - 0.000)^2 + ....

or like this ?

x^2 + ....

Thanks.

### 190: getting small (0.001) differences from correct output

Hi, I have written program for 190 and got WA. I have found correct solution (author claims it was accepted by the judge) on the web and compared my output on a random input (about 10000 cases) and found many small differences (like one of the numbers on the output differed by 0.001 - in about 1% of the cases). I tried to round the output and it ounly caused more diifferences. I also tried to compute the solution in a different way and I also got many small differences. When I compared my two solutions there were also the differences. When I switched to long long, it only increased the differences, when I switched to float it also increased differences; I tried rearranging computattions in my program to reduce this differences but it didn't help much

Could anyone help me find what's wrong with my programs ?

The code is:
the NWAY == 0 case is my first solution, where I compute center of the circle by computing ax+by+c=0 form of lines u, v - in which's intersection center lies, and then simply computiong the intersection

th NWAY != 0 case is my second solution where I compute the intersection directly from equations A + s * B = C + t * D (where A, C are some points and C, D vectors, s, t reals)

Could anyone help me find what's wrong with my programs ?

The code is:

Code: Select all

```
/* @JUDGE_ID: MYID 190 C */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define NWAY 1
#define ROUND 1
#define DEBUG 0
#define EPS 0.000001
#define ISNULL(x) (((x) < EPS && (x) > -EPS) ? 1 : 0)
struct vect {
double x, y;
};
struct line {
double a, b, c;
};
void
paramtoeq (struct vect *p, struct vect *v, struct line *l)
{
if (ISNULL(v->y)) {
l->a = 0;
l->b = 1;
l->c = - (p->y);
} else {
l->a = 1;
l->b = - ((v->x) / (v->y));
l->c = - (l->b * p->y + p->x);
}
}
void
intersection (struct line *a, struct line *b, struct vect *ip)
{
ip->x = (b->c * a->b - a->c * b->b) / (a->a * b->b - a->b * b->a);
ip->y = - (b->c * a->a - a->c * b->a) / (a->a * b->b - a->b * b->a);
}
int
main (void)
{
struct vect p[3], c[2], d[2], cc;
struct line l[2];
double r, t, u;
double g, h, i;
for (;;)
{
if (scanf ("%lf%lf%lf%lf%lf%lf", &(p[0].x), &(p[0].y),
&(p[1].x), &(p[1].y), &(p[2].x), &(p[2].y)) < 6)
break;
c[0].x = (p[0].x + p[1].x) / 2.0;
c[0].y = (p[0].y + p[1].y) / 2.0;
c[1].x = (p[0].x + p[2].x) / 2.0;
c[1].y = (p[0].y + p[2].y) / 2.0;
d[0].x = p[1].y - p[0].y;
d[0].y = - (p[1].x - p[0].x);
d[1].x = p[2].y - p[0].y;
d[1].y = - (p[2].x - p[0].x);
#if NWAY
if (!ISNULL(d[0].y)) {
u = d[0].x / d[0].y;
t = (d[0].y * (c[0].x - c[1].x) - d[0].x * (c[0].y - c[1].y)) /
(d[1].x * d[0].y - d[0].x * d[1].y);
} else {
/* d[1].y will never be null */
t = (c[0].y - c[1].y) / d[1].y;
}
cc.x = c[1].x + t * d[1].x;
cc.y = c[1].y + t * d[1].y;
#else
paramtoeq (c, d, l);
paramtoeq (c+1, d+1, l+1);
intersection (l, l+1, &cc);
#endif
r = hypot (cc.x - p->x, cc.y - p->y);
g = - 2 * cc.x;
h = - 2 * cc.y;
i = cc.x * cc.x + cc.y * cc.y - r * r;
#if ROUND
cc.x = floor (1000.0*cc.x + 0.5) / 1000.0;
cc.y = floor (1000.0*cc.y + 0.5) / 1000.0;
r = floor (1000.0*r + 0.5) / 1000.0;
g = floor (1000.0*g + 0.5) / 1000.0;
h = floor (1000.0*h + 0.5) / 1000.0;
i = floor (1000.0*i + 0.5) / 1000.0;
#endif
printf ("(x %c %.3lf)^2 + (y %c %.3lf)^2 = %.3lf^2\n", (cc.x < -EPS) ? '+' : '-',
fabs(cc.x), (cc.y < -EPS) ? '+' : '-', fabs(cc.y), r);
printf ("x^2 + y^2 %c %.3lfx %c %.3lfy %c %.3lf = 0\n\n",
(g < -EPS) ? '-' : '+', fabs(g), (h < -EPS) ? '-' : '+',
fabs(h), (i < -EPS) ? '-' : '+', fabs(i));
}
return EXIT_SUCCESS;
}
```

th NWAY != 0 case is my second solution where I compute the intersection directly from equations A + s * B = C + t * D (where A, C are some points and C, D vectors, s, t reals)

For example, in C++, the following functions are relatively imprecise, so try to avoid using them if possible:

cos, sin, sqrt

If you have a small floating point error which is ALWAYS present in roughly the same magnitude and/or sign, then it's probably a problem with your equation (or your equation is really imprecise).

I have also tried to rewrite the "correct" solution in c (originally it was in c++) and I also sometimes got slightly different results ...

The only thing I also tried to minimize the error was computing intersections of alll pairs of three lines and taking center of nearest two of them as a center of the circle (which should slightly reduce errors when the points are in som strange positions) but it was almost the same as without it.

Could someone try to check my code (but I am aboluutelu sure that there is not much to be improved) ?

### problem 190 please help !

Hi all ! It's my first post

First, sorry for my english.

So, I try to solve the problem 190. On my computer it runs god (for all test cases from sample input), but I have a WA from the judge. Here's my code:

[cpp]

// the code was cleared

[/cpp]

please somebody, show me my mistake or give me some tricky test case. Thx[/cpp]

First, sorry for my english.

So, I try to solve the problem 190. On my computer it runs god (for all test cases from sample input), but I have a WA from the judge. Here's my code:

[cpp]

// the code was cleared

[/cpp]

please somebody, show me my mistake or give me some tricky test case. Thx[/cpp]

Last edited by wolf on Thu Aug 26, 2004 12:42 pm, edited 2 times in total.

- Ghust_omega
- Experienced poster
**Posts:**115**Joined:**Tue Apr 06, 2004 7:04 pm**Location:**Venezuela

- Ghust_omega
- Experienced poster
**Posts:**115**Joined:**Tue Apr 06, 2004 7:04 pm**Location:**Venezuela

Hi !!!1 wolf i found another bug

I/O

7.0 -5.0 -1.0 1.0 0.0 -6.0

(x - 3.000)^2 + (y + 1.1000)^2 = 5.000^2

x^2 + y^2 - 6.000x + 3.1000y - 12.000 = 0

correct way:

7.0 -5.0 -1.0 1.0 0.0 -6.0

(x - 3.000)^2 + (y + 2.000)^2 = 5.000^2

x^2 + y^2 - 6.000x + 4.000y - 12.000 = 0

and try to use double for all the problems,that implies geometry, in uva its much better use double than float, because produce precisions errors. And dont exist inputs rares like 0 0 0 0 0 0 or 11 22 33 because the 3 points are not in the same line .

Hope it helps

P.S. try not do casting to float a integer becase you can lose information.

I/O

7.0 -5.0 -1.0 1.0 0.0 -6.0

(x - 3.000)^2 + (y + 1.1000)^2 = 5.000^2

x^2 + y^2 - 6.000x + 3.1000y - 12.000 = 0

correct way:

7.0 -5.0 -1.0 1.0 0.0 -6.0

(x - 3.000)^2 + (y + 2.000)^2 = 5.000^2

x^2 + y^2 - 6.000x + 4.000y - 12.000 = 0

and try to use double for all the problems,that implies geometry, in uva its much better use double than float, because produce precisions errors. And dont exist inputs rares like 0 0 0 0 0 0 or 11 22 33 because the 3 points are not in the same line .

Hope it helps

P.S. try not do casting to float a integer becase you can lose information.