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

Lord Nemrod
New poster
Posts: 12
Joined: Mon Mar 28, 2005 7:55 pm
Contact:

Too hard

Post by Lord Nemrod »

I think you've done it too complicatedly. Try to solve the eqations for thee points - you will need only basic mathemathic operations +-* and/. That'd be more precise.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

Also, hypot returns an "int" in ASCII C unless you explicitly declare the function header.

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

190 - Circle Through Three Points

Post by emotional blind »

what is wrong with my solution
it gets wrong answer
my code is very simple
so anybody can look at a glance
have any idea why wa
or have any input for which my solution produce wrong
here is my code.
thanks

Code: Select all

#include <iostream>
#include <stdio.h>
#include <math.h>

using namespace std;

int main (void)
{
	float x1, x2, x3, y1, y2, y3;
	float c, d, e, h, k, r;
	while(scanf("%f%f%f%f%f%f",&x1,&y1,&x2,&y2,&x3,&y3)==6){
		c=((x2*x2+y2*y2-x3*x3-y3*y3)*(y1-y2) - (x1*x1 + y1*y1 - x2*x2 - y2*y2)*(y2-y3))/((x1-x2)*(y2-y3)-(x2-x3)*(y1-y2));
		d=(x1*x1+y1*y1-x3*x3-y3*y3-c*(x3-x1))/(y3-y1);
		e=-1*(x1*x1+y1*y1+c*x1+d*y1);
		h=c/(-2.0);
		k=d/(-2.0);
		r=sqrt(h*h+k*k-e);
		printf("(x %c %.3f)^2 + (y %c %.3f)^2 = %.3f^2\n",(h<0)?'+':'-', (h<0)?(-h):h, (k<0)?'+':'-',(k<0)?(-k):k,r);
		printf("x^2 + y^2 %c %.3fx %c %.3fy %c %.3f = 0\n\n",(c<0)?'-':'+',(c<0)?(-c):c, (d<0)?'-':'+',(d<0)?(-d):d, (e<=0)?'-':'+', (e<0)?(-e):e);
	}
	return 0;
}

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

Post by Ghust_omega »

Hi emotional blind !! try with this input
in:

Code: Select all

5 5 4 7 16 5
out:

Code: Select all

(x - 10.500)^2 + (y - 9.000)^2 = 6.801^2
x^2 + y^2 - 21.000x - 18.000y + 145.000 = 0
Hope it helps
Keep posting !!

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind »

dear Ghust_omega
thanks a lot ...................................
I got ac
thanks again

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind »

dear Ghust_omega
thanks a lot ...................................
I got ac
thanks again

Oyhama Hora
New poster
Posts: 3
Joined: Tue May 24, 2005 10:58 pm

problem 190

Post by Oyhama Hora »

what is wrong with my solution
it gets wrong answer
my code is very simple
so anybody can look at a glance
have any idea why wa
or have any input for which my solution produce wrong
here is my code.
thanks


#include<stdio.h>
#include<math.h>

int z;
float x[3],y[3];
double ak,bk,ck;

void output(void)
{
double r;
r=sqrt(ak*ak+bk*bk-ck);

printf("(x ");
if (-1*ak>0) printf("- ");
else printf("+ ");
printf("%.3f)^2 + (y ",fabs(ak));
if (-1*bk>0) printf("- ");
else printf("+ ");
printf("%.3f)^2 = %.3f",fabs(bk),r);
if (r*r!=r) printf("^2\n");
else printf("\n");

printf("x^2 + y^2 ");
if (2*ak<0) printf("- ");
else printf("+ ");
printf("%.3fx ",fabs(2*ak));
if (2*bk<0) printf("- ");
else printf("+ ");
printf("%.3fy ",fabs(2*bk));
if (ck<0) printf("- ");
else printf("+ ");
printf("%.3f = 0",fabs(ck));
}

void hitung()
{
int i;
double a[6],b[6],p[2],bil[6];
for (i=0;i<3;i++) {
bil=x*x+y*y;
a=x*2;
b=y*2;
}
for (i=3;i<5;i++) {
bil=bil[i-3]-bil[i-2];
a[i]=a[i-3]-a[i-2];
b[i]=b[i-3]-b[i-2];
}
p[0]=a[3];
p[1]=a[4];
for (i=3;i<5;i++) {
bil[i]=bil[i]*fabs(p[4-i]);
b[i]=b[i]*fabs(p[4-i]);
a[i]=a[i]*fabs(p[4-i]);
}
if((p[0]<0&&p[1]<0)||(p[0]>0&&p[1]>0)) {
bil[5]=bil[3]-bil[4];
b[5]=b[3]-b[4];
} else {
bil[5]=bil[3]+bil[4];
b[5]=b[3]+b[4];
}
if(b[5] == 0)
{
bk=0.0;
} else{
bk=-1*bil[5]/b[5];}

if(a[4]== 0.0){
ak=0.0;} else{
ak=(bil[4]*-1+bk*b[4]*-1)/a[4];
}

ck=bil[0]*-1+ak*a[0]*-1+bk*b[0]*-1;
}

main()
{

while (!feof(stdin)) {
fscanf(stdin,"%f %f %f %f %f %f",&x[0],&y[0],&x[1],&y[1],&x[2],&y[2]);
hitung();
output();
printf("\n\n");

}
return 0;
}

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho »

Hi, Oyhama Hora,

First, suppose we have found the equation of the circle
in the following form:

Code: Select all

(X + A)^2 + (Y + B)^2 = R^2
Here we have that R>0 but A and B could have any sign
( they can be zeros as well ).

Then let's suppose that your algorithm is OK so that you
find the correct values for A and B.

Then my question is: what do you print if A==0 ?
And same question for B: if B==0 what do you print ?

Looking at your code ( I haven't compiled and run it )
I think you will print something like:

Code: Select all

(X + 0.000)^2 ... 
which is not correct. Correct output should be

Code: Select all

X^2 ... 
That means the judge wants NO brackets and NO 0.000
in the case A==0 ( B==0 ).

See also the two test cases I have posted here:
http://online-judge.uva.es/board/viewtopic.php?p=35401
I hope this makes the things clear.

Try to change this and see if you still get WA.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho »

I think the two test cases which follow may be helpful
to anyone who still has WA on this problem.

INPUT

Code: Select all

7 0 11 0 9 2
0 9 0 15 3 12
OUTPUT

Code: Select all

(x - 9.000)^2 + y^2 = 2.000^2
x^2 + y^2 - 18.000x + 77.000 = 0

x^2 + (y - 12.000)^2 = 3.000^2
x^2 + y^2 - 24.000y + 135.000 = 0
Good luck to everyone !

nayeemmeeyan
New poster
Posts: 1
Joined: Sat Jul 23, 2005 1:35 pm
Location: bangladesh

why i get worng answer?

Post by nayeemmeeyan »

why i get wrong answer or compile error
this is my code:
#include<stdio.h>
#include<math.h>
int main()
{
double x1,x2,x3,y1,y2,y3,h,k,r,d1,e;
while(scanf("%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3)==6)
{

d1=2*((x2-x1)*(y3-y2)-(x3-x2)*(y2-y1));
h=((y2-y1)*(x3*x3+y3*y3-x2*x2-y2*y2)-(y3-y2)*(x2*x2+y2*y2-x1*x1-y1*y1))/d1;
k=((x3-x2)*(x2*x2+y2*y2-x1*x1-y1*y1)-(x2-x1)*(x3*x3+y3*y3-x2*x2-y2*y2))/d1;
r=sqrt(pow((x1-(-1.0*h)),2)+pow((y1-(-1.0*k)),2));
e=r*r-(h*h+k*k);
if( fabs(h) < 1e-8 && fabs(k)<1e-8)
{
printf("(x + 0.000)^2 + (y + 0.000)^2 = 0.000^2\n",r);
printf("x^2 + y^2 + 0.000x + 0.000y + 0.000 = 0\n",e);
}
else if( h <0 && k <0 && e < 0)
{
h=-1.0*h;
k=-1.0*k;
e=-1.0*e;
printf("(x - %.3lf)^2 + (y - %.3lf)^2 = %.3lf^2\n",h,k,r);
printf("x^2 + y^2 - %.3lfx - %.3lfy + %.3lf = 0\n",2.0*h,2.0*k,e);
}
else if(h < 0 && k< 0 && e>=0)
{
h=-1.0*h;
k=-1.0*k;
printf("(x - %.3lf)^2 + (y - %.3lf)^2 = %.3lf^2\n",h,k,r);
printf("x^2 + y^2 - %.3lfx - %.3lfy - %.3lf = 0\n",2.0*h,2.0*k,e);
}
else if( h >=0 && k <0 && e<0)
{
k=-1.0*k;
e=-1.0*e;
printf("(x + %.3lf)^2 + (y - %.3lf)^2 = %.3lf^2\n",h,k,r);
printf("x^2 + y^2 + %.3lfx - %.3lfy + %.3lf = 0\n",2.0*h,2.0*k,e);
}
else if(h>=0 && k<0 && e>=0)
{
k=-1.0*k;
printf("(x + %.3lf)^2 + (y - %.3lf)^2 = %.3lf^2\n",h,k,r);
printf("x^2 + y^2 + %.3lfx - %.3lfy - %.3lf = 0\n",2.0*h,2.0*k,e);
}
else if(h <0 && k>=0 && e< 0)
{
e=-1.0*e;
h=-1.0*h;
printf("(x - %.3lf)^2 + (y + %.3lf)^2 = %.3lf^2\n",h,k,r);
printf("x^2 + y^2 - %.3lfx + %.3lfy + %.3lf = 0\n",2.0*h,2.0*k,e);
}
else if(h<0 && k>=0 && e>=0)
{
h=-1.0*h;
printf("(x - %.3lf)^2 + (y + %.3lf)^2 = %.3lf^2\n",h,k,r);
printf("x^2 + y^2 - %.3lfx + %.3lfy - %.3lf = 0\n",2.0*h,2.0*k,e);
}
else if(h>=0 && k>=0 && e<0)
{
printf("(x + %.3lf)^2 + (y + %.3lf)^2 = %.3lf^2\n",h,k,r);
printf("x^2 + y^2 + %.3lfx + %.3lfy + %.3lf = 0\n",2.0*h,2.0*k,e);

}
else//(h>=0 && k>=0 && e>=0)
{
printf("(x + %.3lf)^2 + (y + %.3lf)^2 = %.3lf^2\n",h,k,r);
printf("x^2 + y^2 + %.3lfx + %.3lfy - %.3lf = 0\n",2.0*h,2.0*k,e);
}
printf("\n");
}
return 0;
}

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 »

I have three points to make:

1) Which problem is this code supposed to solve?
2) What is the algorithm used?
3) I believe you are solving problem 190. You can search for past threads on problem 190.

Isaac
New poster
Posts: 1
Joined: Thu Sep 08, 2005 9:20 pm
Location: Taiwan

Re: still confuse

Post by Isaac »

gracia wrote:well.. thank you for your answer
and i have tried your advice
but i still got WA
this is my program and may be you can tell me why i got WA :D

...

int main()
{
while (!feof(stdin)) {
fscanf(stdin,"%f %f %f %f %f %f",&x[0],&y[0],&x[1],&y[1],&x[2],&y[2]);
hitung();
output();
printf("\n\n");
}
return 0;
}
Dear gracia,

I know it's a little late.
but I think your program has some problem when it reads six numbers from the system.

Because the lack of practice in I/O,
I tried to use your method after many failed.

It's fine when I tested it on my PC,
but when I pressed Ctrl + C to end the program in Dev-C++

It printed something on the screen before close.

then I found another article
http://online-judge.uva.es/board/viewtopic.php?p=35401

I tried the method that 'emotional blind' san use in his program,
and I got an AC.

I think the hint that 'Sedefcho' san post in that article is also useful, but I don't know if it's really matter because i changed my program lots of times before I found the problem about input.

--
Please forgive my poor english...

nukeu666
New poster
Posts: 44
Joined: Sun Feb 13, 2005 1:13 am
Location: India
Contact:

190 wa

Post by nukeu666 »

where am i going wrong or gimma an input that doesn work

Code: Select all

#include<math.h>
#include<stdio.h>
int main()
{
  double con,cenx,ceny,rad,ax,ay,bx,by,cx,cy,mab,mac,p1,q1,r1,p2,q2,r2;
  int sx,sy,sc;
while(scanf("%lf %lf %lf %lf %lf %lf",&ax,&ay,&bx,&by,&cx,&cy)==6)
  {
    sx=0,sy=0,sc=0;
    mab=(by-ay)/(bx-ax);
    mac=(cy-ay)/(cx-ax);
    p1=mab;p2=mac;
    q1=1;q2=1;
    r1=(ax+bx)/2+mab*(ay+by)/2;
    r2=(ax+cx)/2+mac*(ay+cy)/2;
    cenx=(r1*p2-r2*p1)/(q1*p2-q2*p1);
    ceny=(q2*r1-q1*r2)/(q2*p1-p2*q1);
    rad=pow(pow((cenx-ax),2)+pow((ceny-ay),2),0.5);
    if(cenx<0)
      sx=1;
    if(ceny<0)
      sy=1;
    if((con=pow(cenx,2)+pow(ceny,2)-pow(rad,2))<0)
      sc=1;
    if(fabs(cenx)<.001)
      printf("x^2 ");
    else
      {
        if(sx==0)
          printf("(x - %.3lf)^2 + ",cenx);
        else
          printf("(x + %.3lf)^2 + ",-cenx);
      }
    if(fabs(ceny)<.001)
      printf("y^2 = %.3lf^2",fabs(rad));
    else
      {
        if(sy==0)
          printf("(y - %.3lf)^2 = %.3lf^2",ceny,fabs(rad));
        else
          printf("(y + %.3lf)^2 = %.3lf^2",-ceny,fabs(rad));
      }

      printf("\nx^2 + y^2 ");
    if(sx==0&&fabs(cenx)>.001)
      printf("- %.3lfx ",2*fabs(cenx));
    if(sx==1&&fabs(cenx)>.001)
      printf("+ %.3lfx ",-(2*cenx));
    if(sy==0&&fabs(ceny)>.001)
      printf("- %.3lfy ",2*fabs(ceny));
    if(sy==1&&fabs(ceny)>.001)
      printf("+ %.3lfy ",-(2*ceny));
    if(sc==1&&fabs(con)>.001)
      printf("- %.3lf ",-con);
    if(sc==0&&fabs(con)>.001)
      printf("+ %.3lf ",fabs(con));
    printf("= 0\n\n");
  }
}
input

Code: Select all

7.0 -5.0 -1.0 1.0 0.0 -6.0
1.0 7.0 8.0 6.0 7.0 -2.0
0 0 5 0 2.5 2.5
output

Code: Select all

(x - 3.000)^2 + (y + 2.000)^2 = 5.000^2
x^2 + y^2 - 6.000x + 4.000y - 12.000 = 0

(x - 3.921)^2 + (y - 2.447)^2 = 5.409^2
x^2 + y^2 - 7.842x - 4.895y - 7.895 = 0

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

Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

Post by Rocky »

i get the following output for those input from accepted code..

Code: Select all

(x - 3.000)^2 + (y + 2.000)^2 = 5.000^2
x^2 + y^2 - 6.000x + 4.000y - 12.000 = 0

(x - 3.921)^2 + (y - 2.447)^2 = 5.409^2
x^2 + y^2 - 7.842x - 4.895y - 7.895 = 0

(x - 2.500)^2 + (y + 0.000)^2 = 2.500^2
x^2 + y^2 - 5.000x - 0.000y - 0.000 = 0
may be it help

GOOD LUCK
Rocky

xintactox
New poster
Posts: 14
Joined: Thu Dec 01, 2005 3:17 pm
Location: Brazil

190-Circle Through Three points -WA-Already read past posts!

Post by xintactox »

Hi everybody!

I'm getting WA in problem 190 - Circle through three points over and over again...

Can someone please check my code, maybe u can find where it's wrong....
I need some critical test cases or something...

For the following input:

Code: Select all

7.0 -5.0 -1.0 1.0 0.0 -6.0 
1.0 7.0 8.0 6.0 7.0 -2.0 
0 0 5 0 2.5 2.5 
my program generates the following output

Code: Select all

(x - 3.000)^2 + (y + 2.000)^2 = 5.000^2 
x^2 + y^2 - 6.000x + 4.000y - 12.000 = 0 

(x - 3.921)^2 + (y - 2.447)^2 = 5.409^2 
x^2 + y^2 - 7.842x - 4.895y - 7.895 = 0 

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

I already read all the past posts about this problem, sorry for bothering you all :)

I've also read about the output with zeros, like the third case of my output... some people say it must me made like i did, other people says that it must be without the brackets or zeros.... What's correct?

My code follows :)

Code: Select all

#include <iostream>
#include <stdio.h>
#include <math.h>

using namespace std;

class point
{
	public:
		double x, y;
		
};

int main()
{
	point p1, p2, p3;
	double ma, mb, h, k, r, c, d, e;
	while(cin>>p1.x)
	{
		cin>>p1.y>>p2.x>>p2.y>>p3.x>>p3.y;
		ma = (p2.y - p1.y)/(p2.x - p1.x);
		mb = (p3.y - p2.y)/(p3.x - p2.x);
		h = (ma*mb*(p1.y - p3.y) + mb*(p1.x + p2.x) - ma*(p2.x + p3.x))/(2.0*(mb - ma));		
		k = (-1.0/(ma+0.000001))*(h - ((p1.x + p2.x))/2) + (p1.y + p2.y)/2.0;					
		r = sqrt((h - p1.x)*(h - p1.x)+(k - p1.y)*(k - p1.y));
								
		//cout<<"c = "<<c<<endl;
		//cout<<"d = "<<d<<endl;
				
		if(h >= 0.000001)
			printf("(x - %.3f)^2 + (y ", fabs(h));
		else
			printf("(x + %.3f)^2 + (y ", fabs((-1)*h));
		
		if(k >= 0.000001)
			printf("- %.3f)^2 = %.3f^2", fabs(k), fabs(r));
		else
			printf("+ %.3f)^2 = %.3f^2", fabs((-1)*k),fabs(r));		
		
		c = 2.0*h;
		d = 2.0*k;
		e = (h*h) + (k*k) - (r*r);
		
		
		if(c >= 0.001){
		if(c >= 0.00000001)
			printf("\nx^2 + y^2 - %.3fx ", fabs(c));
		else
			printf("\nx^2 + y^2 + %.3fx ", fabs(c));}
		else printf("\nx^2 + y^2 + %.3fx ", fabs(c));	
		
		if(d >= 0.001){
		if(d >= 0.00000001)
			printf("- %.3fy ", fabs(d));
		else
			printf("+ %.3fy ", fabs(d));}
		else if(d == 0.000) printf("- %.3fy ", fabs(d));
		else printf("+ %.3fy ", fabs(d));
		
		if(e > 0.00000001)
			printf("+ %.3f = 0\n", fabs(e));
		else
			printf("- %.3f = 0\n", fabs(e));
		
		printf("\n");		
	}
	return 0;
}
Please help me!

Thank you all and happy new year!

Post Reply

Return to “Volume 1 (100-199)”