190 - Circle Through Three Points

[koniloni]

Can you tell me, how can I find the center from three points?

[ftomi]

X(O) = (X(A)+X(B)+X(C))/3
Y(O) = (Y(A)+Y(B)+Y(C))/3

[koniloni]

I have not understand from your mail.Can you give me clear concept?What will be the center of circle ,if I input following points?
7.0 -5.0 -1.0 1.0 0.0 -6.0 and
1.0 7.0 8.0 6.0 7.0 -2.0
Please show me the calculation.

[ftomi]

first case:
Center's x-coordiante: (7.0 + -1.0 + 0.0) / 3 = 2.00
Center's y-coordiante: (-5.0 + 1.0 + -6.0) / 3 = -3.33

second case:
Center's x-coordiante: (1.0 + 8.0 + 7.0) / 3 = 5.33
Center's y-coordiante: (7.0 + 6.0 + -2.0) / 3 = 3.66

[koniloni]

How can I change +/- sign in this problem? I think,in this problem ( h,k) is the center point. But, sample input and output what is given in the question do not match with your solution. Here is the sample input and output :

Sample input

7.0 -5.0 -1.0 1.0 0.0 -6.0
1.0 7.0 8.0 6.0 7.0 -2.0

Sample output

(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

I think here the center point for the first one is (3.000,-2.000)
and second one is (3.921,2.447).
But, from your solution I think center point for the first one is (2.00,-3.33) and second one is (5.33,3.66).
Please , give me clear concept.

[ftomi]

Hi! My previous post is bad, you are right. So, the correct one:
You shuold calculate two bisector's intersection.
Every bisector passing through the corresponding midpoint,
and every bisector's direction vector is the normal vector
of the triangle's corresponding side. So you can easily
write the bisector's equation.

The needed statements: (copy it to notepad to see right if you have small monitor)

Code: Select all

The midpoint's coordinates of section AB:

         A  + B      A  + B
          x    x      y    y
  P    (--------- ; ---------)    (1)
   mid      2           2


The direction vector of section AB:

v (B  - A  ; B  - A )    (2)
    x    x    y    y


The normalvector of a direction vector v (v  ; v ):
                                           1    2

n (-v  ; v )    (3)
     2    1


Line's equatoin passing through point
P (x  ; y ) direction v (v  ; v ) is:
    0    0                1    2
                                 
  v  X - v  Y = v  x  - v  y     (4)
   2      1      2  0    1  0


That's all.
The calculation:

Section AB's direction vector is from (2):

v (B  - A  ; B  - A )    (5)
    x    x    y    y


Section AB's normal vector is from (5) and (3):

v (A  - B  ; B  - A )    (6)
    y    y    x    x


The equation of bisector of section AB is
from (4) and (5) and (6) and (1):

                                   A  + B             A  + B
                                    x    x             y    y
(B  - A )X + (B  - A )Y = (B  - A )------- + (B  - A )-------  (7)
  x    x       y    y       x    x    2        y    y   2


It's equal to:

                                 2    2    2    2
2 (B  - A ) X + 2 (B  - A ) Y = B  - A  + B  - A     (8)
    x    x          y    y       x    x    y    y


The equation of bisector of section AC is in the same way:

                                 2    2    2    2
2 (C  - A ) X + 2 (C  - A ) Y = C  - A  + C  - A      (9)
    x    x          y    y       x    x    y    y

You have nothing to do, just solve this two equation: two unknown
variable - two equation. Examine theses as a*x+b*y = c, and try to
solve it that way. Do not bring the variables anymore!

Good luck!

[galois_godel]

program a190(input,output);

type geshi=record
str:string[3];
val:real;
zero:boolean;
behind:char;
end;

var
x0,x1,x2,y1,y2,y0:real;
hkcde:array[1..5]of geshi;
r,h,k:real;
procedure getstr;
var i:integer;
begin
for i:=1 to 5 do
begin
hkcde.str:=' + ';
hkcde.zero:=false;
hkcde.behind:=' ';
if hkcde.val=0 then hkcde.zero:=true
else
begin
if hkcde.val<0 then
hkcde.str:=' - ';
end;
if i=3 then hkcde.behind:='x';
if i=4 then hkcde.behind:='y';
hkcde.val:=abs(hkcde[i].val);
end;
end;

begin
// Insert user code here
while not eof(input) do
begin
readln(x0,y0,x1,y1,x2,y2);
x1:=x1-x0;
y1:=y1-y0;
x2:=x2-x0;
y2:=y2-y0;
if y1=0 then begin
hkcde[1].val:=0.5*x1+x0;
h:=hkcde[1].val-x0;
hkcde[2].val:=y0-x2*(x1-x2)/(2*y2)+y2/2;
k:=hkcde[2].val-y0;
end
else
begin
if y2=0 then begin
hkcde[1].val:=0.5*x2+x0;
h:=hkcde[1].val-x0;
hkcde[2].val:=y0-x1*(x2-x1)/(2*y1)+y1/2;
k:=hkcde[2].val-y0;
end
else begin
hkcde[1].val:=x0+0.5*((x1*x1/y1-x2*x2/y2)-(y2-y1))/(x1/y1-x2/y2);
h:=hkcde[1].val-x0;
hkcde[2].val:=y0+0.5*y1-(x1/y1)*(h-x1/2);
k:=hkcde[2].val-y0; end;end;
r:=sqrt(h*h+k*k);
h:=h+x0;
k:=k+y0;
hkcde[1].val:=-hkcde[1].val;
hkcde[2].val:=-hkcde[2].val;
hkcde[3].val:=2*hkcde[1].val;
hkcde[4].val:=2*hkcde[2].val;
hkcde[5].val:=h*h+k*k-r*r;
getstr;
if hkcde[1].zero then write('x^2 + ')
else
begin
write('(x',hkcde[1].str,hkcde[1].val:0:3,')^2 + ');
end;
if hkcde[2].zero then writeln('y^2 = ',r:0:3,'^2')
else
writeln('(y',hkcde[2].str,hkcde[2].val:0:3,')^2 = ',r:0:3,'^2');
write('x^2 + y^2');
if not(hkcde[3].zero) then
begin
write(hkcde[3].str);
if hkcde[3].val<>1 then write(hkcde[3].val:0:3);
write(hkcde[3].behind);
end;
if not(hkcde[4].zero) then
begin
write(hkcde[4].str);
if hkcde[4].val<>1 then write(hkcde[4].val:0:3);
write(hkcde[4].behind);
end;
if not(hkcde[5].zero) then
write(hkcde[5].str,hkcde[5].val:0:3);
writeln(' = 0');
writeln;
end;
end.

[galois_godel]

#include <iostream.h>
#include <stdio.h>
#include <math.h>
double centerx,centery,w,h;
int point(double a,double b,double c,double x,double y,double std)
{
double mm=a*y+b*x+c;
if(mm*std>0)
return 1;
else
return 0;
}
double abs(double x)
{
if(x<0)
return (-x);
else
return x;
}
int isinrect(double x,double y)
{
if((abs(x-centerx)<=w)&&(abs(y-centery)<=h))
return 1;
else
return 0;
}
int iscrossx(double x1,double x2)
{
if((x1-centerx)*(x2-centerx)<0)
return 1;
else
return 0;
}
int iscrossy(double x1,double x2)
{
if((x1-centery)*(x2-centery)<0)
return 1;
else
return 0;
}

void main(void)
{
int n;
cin>>n;
int ii;
double xs,ys,xe,ye,xl,yt,xr,yb;
for(ii=0;ii<n;ii++)
{
cin>>xs>>ys>>xe>>ye>>xl>>yt>>xr>>yb;
double a,b,c;
char res='T';
a=xs-xe;
b=ye-ys;
c=(ys-ye)*xs-(xs-xe)*ys;
double std;
std=a*yt+b*xl+c;
if((std!=0)&&(point(a,b,c,xr,yb,std)*point(a,b,c,xl,yb,std)*point(a,b,c,xr,yt,std)!=0))
{
res='F';
}

centerx=(xl+xr)/2;
centery=(yt+yb)/2;

w=abs(xl-centerx);
h=abs(yb-centery);
if(!(isinrect(xs,ys)||isinrect(xe,ye)||iscrossx(xe,xs)||iscrossy(ye,ys)))
res='F';
cout<<res<<endl;
}
}

[Moni]

Can anybody tell me what is wrong with this code ???

[cpp]
#include<iostream.h>
#include<iomanip.h>
#include<math.h>

int main()
{
double Ax,Ay,Bx,By,Cx,Cy;

while(cin >> Ax >> Ay >> Bx >> By >> Cx >> Cy)
{
double m1=-1*((Bx-Ax)/(By-Ay));
double c1=((Ay+By)/2)+((Ax+Bx)/2)*((Bx-Ax)/(By-Ay));

double m2=-1*((Cx-Ax)/(Cy-Ay));
double c2=((Ay+Cy)/2)+((Ax+Cx)/2)*((Cx-Ax)/(Cy-Ay));

double h=(c2-c1)/(m1-m2);
double k=m1*(c2-c1)/(m1-m2)+c1;

double rr=(Ax-h)*(Ax-h)+(Ay-k)*(Ay-k);

double c=-2*h;
double d=-2*k;
double e=h*h+k*k-rr;

cout << setiosflags(ios::fixed|ios::showpoint) << setprecision(3);

cout << "(x ";

if(h>=0)
cout << "- " << h;
else
cout << "+ " << -h;

cout << ")^2 + (y ";

if(k>=0)
cout << "- " << k;
else
cout << "+ " << -k;

cout << ")^2 = ";

cout << sqrt(rr) << "^2" << endl;

cout << "x^2 + y^2 ";

if(c>=0)
cout << "+ " << c << "x ";
else
cout << "- " << -c << "x ";

if(d>=0)
cout << "+ " << d << "y ";
else
cout << "- " << -d << "y ";

if(e>=0)
cout << "+ " << e << " = 0" << endl;
else
cout << "- " << -e << " = 0" << endl;

cout << endl;
}

return 0;
}
[/cpp]

Isn't it a good code !!!

[Balon]

you should pay more attention on the casting between float number to an integer:
if some expression results float number 0, you may got -0.00000000001 for example, then if you cast it to integer, you may got -0, not 0!!
here is my code , it is complex, but it's right

[cpp]

#include <iostream>
#include <cmath>
#include <string>
#include <cstdio>

using namespace std;

istream& FIN = cin;
ostream& OUT = cout;

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

int N;
POINT pt[3];
POINT cen;
double r;
double c, d, e;
string form1, form2;

void Circle();
void Form();
void proc();

int main()
{
bool bFirst = true;
int i, j, k;

for(int c=0; ; ++c)
{
FIN>> ws;
if(FIN.eof())
break;
for(i=0; i<3; ++i)
FIN>> pt.x>> pt.y;
Circle();
bFirst = false;
proc();
OUT<< endl;
}
return 0;
}

void Circle()
{
double x01 = pt[1].x - pt[0].x;
double y01 = pt[1].y - pt[0].y;
double x02 = pt[2].x - pt[0].x;
double y02 = pt[2].y - pt[0].y;
double z1 = x01 * (pt[0].x + pt[1].x) + y01 * (pt[0].y + pt[1].y);
double z2 = x02 * (pt[0].x + pt[2].x) + y02 * (pt[0].y + pt[2].y);
double dd = 2.0 * (x01 * (pt[2].y - pt[1].y) - y01 * (pt[2].x - pt[1].x));
cen.x = (y02 * z1 - y01 * z2) / dd;
cen.y = (x01 * z2 - x02 * z1) / dd;
r = sqrt((pt[0].x - cen.x)*(pt[0].x - cen.x) + (pt[0].y - cen.y) * (pt[0].y - cen.y));
c = -2.0 * cen.x;
d = -2.0 * cen.y;
e = (cen.x * cen.x) + (cen.y * cen.y) - (r * r);
}

void Form()
{
char buf[20];
long x0, y0, r0;
long c0, d0, e0;
int sigx, sigy, sigr, sigc, sigd, sige;

sigx = (cen.x < 0) ? -1 : 1;
sigy = (cen.y < 0) ? -1 : 1;
sigr = (r < 0) ? -1 : 1;
sigc = (c < 0) ? -1 : 1;
sigd = (d < 0) ? -1 : 1;
sige = (e < 0) ? -1 : 1;
x0 = ((long)(fabs(cen.x) * 1000 + 0.5)) * sigx;
y0 = ((long)(fabs(cen.y) * 1000 + 0.5)) * sigy;
r0 = ((long)(fabs(r) * 1000 + 0.5)) * sigr;
c0 = ((long)(fabs(c) * 1000 + 0.5)) * sigc;
d0 = ((long)(fabs(d) * 1000 + 0.5)) * sigd;
e0 = ((long)(fabs(e) * 1000 + 0.5)) * sige;

char op[5];
op[0] = (x0 > 0) ? '-' : '+';
op[1] = (y0 > 0) ? '-' : '+';
op[2] = (c0 < 0) ? '-' : '+';
op[3] = (d0 < 0) ? '-' : '+';
op[4] = (e0 < 0) ? '-' : '+';
x0 = abs(double(x0));
y0 = abs(double(y0));
r0 = abs(double(r0));
c0 = abs(double(c0));
d0 = abs(double(d0));
e0 = abs(double(e0));

sprintf(buf, "(x %c ", op[0]);
form1 = string(buf);
sprintf(buf, "%.3f)^2 + (y %c ", x0/1000.0, op[1]);
form1 += string(buf);
sprintf(buf, "%.3f)^2 = ", y0/1000.0);
form1 += string(buf);
sprintf(buf, "%.3f^2", r0/1000.0);
form1 += string(buf);

sprintf(buf, "x^2 + y^2 %c ", op[2]);
form2 = string(buf);
sprintf(buf, "%.3fx %c ", c0/1000.0, op[3]);
form2 += string(buf);
sprintf(buf, "%.3fy %c ", d0/1000.0, op[4]);
form2 += string(buf);
sprintf(buf, "%.3f = 0", e0/1000.0);
form2 += string(buf);
}

void proc()
{
Form();
OUT<< form1<< endl;
OUT<< form2<< endl;
}

[/cpp]

[Moni]

I have to know more about :

if some expression results float number 0, you may got -0.00000000001 for example, then if you cast it to integer, you may got -0, not 0!!

Can you give me some examples with C/C++ code ???

[vinchen]

i got a compiling error message:
01283424_24.c:7: parse error before `&'
01283424_24.c: In function `main':
01283424_24.c:70: `EOF' undeclared (first use in this function)
01283424_24.c:70: (Each undeclared identifier is reported only once
01283424_24.c:70: for each function it appears in.)

here is my code
[c]
&#65279;#include<stdio.h>
#include<math.h>
double midpoint(double p1, double p2)
{
double result;
result=( p1 + p2 )/ 2;
return result;
}

double delta( double num1, double num2, double num3, double num4 )
{
double num_result;
num_result =( num1 * num4 )-( num2*num3 );
return num_result;
}

double radius(double p,double q,double r, double s)
{
double distance,rad;
distance=(pow(r-p,2)) + ( pow(s-q,2) );
rad=pow(distance, .5);
return rad;
}

void circle (double xc,double yc,double rc)
{
if( (xc>=0) && (yc>=0))
printf("(x - %.3f)^2 + (y - %.3f)^2 = %.3f^2\n",xc,yc,rc);
if( (xc>=0) && (yc<0) )
printf("(x - %.3f)^2 + (y + %.3f)^2 = %.3f^2\n",xc,-1*yc,rc);
if((xc<0)&&(yc>=0))
printf("(x + %.3f)^2 + (y - %.3f)^2 = %.3f^2\n",-1*xc,yc,rc);
if((xc<0)&&(yc<0))
printf("(x + %.3f)^2 + (y + %.3f)^2 = %.3f^2\n",-1*xc,-1*yc,rc);
}

void extract ( double xex,double yex,double rex)
{
double s1,s2,s3;
s1=2*xex;
s2=2*yex;
s3= ( pow(xex,2)+pow(yex,2) ) - pow(rex,2) ;
if((s1>=0)&&(s2>=0)&&(s3>=0))
printf("x^2 + y^2 - %.3fx - %.3fy + %.3f = 0\n",s1,s2,s3);
if((s1>=0)&&(s2<0)&&(s3<0))
printf("x^2 + y^2 - %.3fx + %.3fy - %.3f = 0\n",s1,-1*s2,-1*s3);
if((s1>=0)&&(s2>=0)&&(s3<0))
printf("x^2 + y^2 - %.3fx - %.3fy - %.3f = 0\n",s1,s2,-1*s3);
if((s1>=0)&&(s2<0)&&(s3>=0))
printf("x^2 + y^2 - %.3fx + %.3fy + %.3f = 0\n",s1,-1*s2,s3);
if((s1<0)&&(s2>=0)&&(s3>=0))
printf("x^2 + y^2 + %.3fx - %.3fy + %.3f = 0\n",-1*s1,s2,s3);
if((s1<0)&&(s2>=0)&&(s3<0))
printf("x^2 + y^2 + %.3fx - %.3fy - %.3f = 0\n",-1*s1,s2,-1*s3);
if((s1<0)&&(s2<0)&&(s3>=0))
printf("x^2 + y^2 + %.3fx + %.3fy + %.3f = 0\n", -1*s1,-1*s2,s3);
if((s1<0)&&(s2<0)&&(s3<0))
printf("x^2 + y^2 + %.3fx + %.3fy - %.3f = 0\n",-1*s1,-1*s2,-1*s3);
}

int main( void )
{
double a1,a2,b1,b2,c1,c2,d1,d2,e1,e2,con1,con2,del,delx,dely,x,y,r;
while( scanf("%lf %lf %lf %lf %lf %lf", & a1, & a2, & b1, & b2, & c1, & c2 ) != EOF )
{
d1=midpoint(a1,b1);
d2=midpoint(a2,b2);
e1=midpoint(b1,c1);
e2=midpoint(b2,c2);
con1=((a1-b1)*d1)+((a2-b2)*d2);
con2=((b1-c1)*e1) + ((b2-c2)*e2);
del=delta( a1-b1, a2-b2, b1-c1, b2-c2 );
delx=delta( con1,a2-b2,con2,b2-c2 );
dely=delta( a1-b1,con1,b1-c1,con2 );
x=delx/del;
y=dely/del;
r=radius(x,y,a1,a2);
circle(x,y,r);
extract(x,y,r);
}
return 0;
}

Code: Select all

can anyone help me? thanx
BTW i use cc to compile at home, and it's OK 

[/c]

[the LA-Z-BOy]

i think you got messed up by your mailing program if you've e mailed your program...
first read the instructions at
http://acm.uva.es/problemset/howtows.html#java
or you can directly submit problems at
http://acm.uva.es/problemset/submit.php

hope that works
___________
the LA-Z-BOY

[gracia]

can u give me sample input and sample output for this case
i've got WA

[Jalal]

u may not need sample input or output if u follow the following process:
just print:
(x - 0.000)^2 + (y - 0.000)^2 = 0.000
x^2 + y^2 + 0.000x + 0.000y + 0.000 = 0
when the inputs are all 0.