190 - Circle Through Three Points

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Partha
New poster
Posts: 5
Joined: Fri Mar 28, 2003 8:51 pm
Location: Bangladesh
Contact:

Post by Partha » Tue Apr 08, 2003 4:00 pm

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.

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

Post by Moni » Wed May 07, 2003 9:07 pm

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 !!!
ImageWe 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

Post by dioniz69 » Wed Jul 23, 2003 11:52 am

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

Post by dioniz69 » Thu Jul 24, 2003 2:42 am

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

Post by Andrej » Sat Dec 13, 2003 7:17 pm

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

Post by skeeve » Mon Apr 19, 2004 9:10 pm

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

Post by junbin » Tue Apr 20, 2004 10:13 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

Post by skeeve » Tue Apr 20, 2004 12:07 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

problem 190 please help !

Post by wolf » Sun Aug 22, 2004 4:34 am

Hi all ! It's my first post :-D
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 :-D
[/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.

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

Post by jagadish » Sun Aug 22, 2004 7:47 am

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

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

Post by Ghust_omega » Tue Aug 24, 2004 11:20 am

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

Post by wolf » Tue Aug 24, 2004 12:35 pm

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

Post by wolf » Wed Aug 25, 2004 1:46 pm

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

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

Post by Ghust_omega » Thu Aug 26, 2004 6:59 am

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

Post by wolf » Thu Aug 26, 2004 12:40 pm

Thanks ghust_omega I got an AC now !!! :-D

Post Reply

Return to “Volume 1 (100-199)”