## 190 - Circle Through Three Points

Moderator: Board moderators

Partha
New poster
Posts: 5
Joined: Fri Mar 28, 2003 8:51 pm
Contact:
Hey...for input

0 0 5 0 2.5 2.5

my accepted program's output is:

(x - 2.500)^2 + (y + 0.000)^2 = 2.500^2
x^2 + y^2 - 5.000x + 0.000y + 0.000 = 0

So '0.000' doesn't make any sence here...
I think eric's output is correct.

Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:
Oh! Again that 190..........

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!

dioniz69
New poster
Posts: 3
Joined: Wed Jul 23, 2003 11:45 am

### 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]

dioniz69
New poster
Posts: 3
Joined: Wed Jul 23, 2003 11:45 am

### 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;
}
}

Andrej
New poster
Posts: 1
Joined: Sat Dec 13, 2003 7:06 pm

### 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.

skeeve
New poster
Posts: 6
Joined: Sun Apr 18, 2004 4:17 pm

### 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:

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;
}
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)

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
If you have a small floating point error which occurs RANDOMLY, it probably means that your equations are not precise enough. Try to optimize your equations by removing the functions that reduce the precision.

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).

skeeve
New poster
Posts: 6
Joined: Sun Apr 18, 2004 4:17 pm
The error is present only in some of the outputs, and th difference is sometimes 0.001 and sometimes -0.001; The only "precision reducing function" I use in my program is hypot when computing r but the errors usually occur in center coordinates or in the las valur (cx^2 + cy^2 -r^2). Most often they occur just in one of the values.
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) ?

wolf
New poster
Posts: 34
Joined: Sun Aug 22, 2004 4:20 am
Location: Poland

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]
Last edited by wolf on Thu Aug 26, 2004 12:42 pm, edited 2 times in total.

Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA
maybe you dont take care of the case when all co-ordinates of triangle negative or with sides of slope 0 or infinity.
example:
-1.0 -1.0 -2.0 -2.0 -3.0 -1.0

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela
Hii!!! wolf look i found this in I/O
input
0 -2 0 2 2 0
ouput
(x - 0.000)^2 + (y - 0.000)^2 = 2.000^2
x^2 + y^2 - 0.000x - 0.000y - 4.000 = 0

Correct way

(x + 0.000)^2 + (y + 0.000)^2 = 2.000^2
x^2 + y^2 + 0.000x + 0.000y - 4.000 = 0

try to check this
Hope it help

wolf
New poster
Posts: 34
Joined: Sun Aug 22, 2004 4:20 am
Location: Poland
Thank you for help. I repaired the bugs (test cases from you works perfect), but still WA. Can somebody give me more test cases for this problem (with correct answers) ?

wolf
New poster
Posts: 34
Joined: Sun Aug 22, 2004 4:20 am
Location: Poland
Thank you for help. I repaired the bugs (test cases from you works perfect), but still WA. Can somebody give me more test cases for this problem (with correct answers) ?

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.

wolf
New poster
Posts: 34
Joined: Sun Aug 22, 2004 4:20 am
Location: Poland
Thanks ghust_omega I got an AC now !!!