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

koniloni
New poster
Posts: 15
Joined: Thu Apr 18, 2002 5:10 am

problem 190

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

ftomi
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:
X(O) = (X(A)+X(B)+X(C))/3
Y(O) = (Y(A)+Y(B)+Y(C))/3

koniloni
New poster
Posts: 15
Joined: Thu Apr 18, 2002 5:10 am

Help problem 190

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
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:
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
New poster
Posts: 15
Joined: Thu Apr 18, 2002 5:10 am

Help problem 190

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
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:
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
New poster
Posts: 17
Joined: Wed Jul 17, 2002 5:00 pm

190 WR?why?(or u can give me some sample input and output)

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
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
New poster
Posts: 17
Joined: Wed Jul 17, 2002 5:00 pm

190 WR?why?(or u can give me some sample input and output)

#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
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:

190 O through . . and .

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 !!!
We are all in a circular way, no advances, only moving and moving!

Balon
New poster
Posts: 8
Joined: Tue Nov 26, 2002 6:00 am
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
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:
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 ???
We are all in a circular way, no advances, only moving and moving!

vinchen
New poster
Posts: 1
Joined: Sun Dec 08, 2002 5:48 pm

190...compiling error

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)
{
distance=(pow(r-p,2)) + ( pow(s-q,2) );
}

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;
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
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Contact:
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
New poster
Posts: 5
Joined: Mon Nov 25, 2002 9:04 am
Location: jakarta

190- sample input

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

Jalal
Learning poster
Posts: 65
Joined: Sun Jun 02, 2002 8:41 pm