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

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

problem 190

Post by koniloni » Tue May 28, 2002 7:50 am

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:

Post by ftomi » Wed May 29, 2002 9:09 am

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

Post by koniloni » Sat Jun 01, 2002 6:44 am

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:

Post by ftomi » Sun Jun 02, 2002 8:15 pm

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

Post by koniloni » Sat Jun 08, 2002 6:27 am

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:

Post by ftomi » Mon Jun 10, 2002 1:14 am

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)

Post by galois_godel » Tue Aug 13, 2002 3:56 pm

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

Post by galois_godel » Tue Aug 13, 2002 4:01 pm

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

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

190 O through . . and .

Post by Moni » Sat Nov 23, 2002 9:42 pm

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

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

Post by Balon » Tue Nov 26, 2002 3:16 pm

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
:wink:
[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]

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

Post by Moni » Fri Nov 29, 2002 9:52 pm

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

Post by vinchen » Sun Dec 08, 2002 5:53 pm

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]

User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy » Mon Dec 09, 2002 10:02 pm

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 :lol:
___________
the LA-Z-BOY

gracia
New poster
Posts: 5
Joined: Mon Nov 25, 2002 9:04 am
Location: jakarta

190- sample input

Post by gracia » Fri Jan 03, 2003 11:03 am

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
Location: BANGLADESH
Contact:

Post by Jalal » Fri Jan 03, 2003 6:45 pm

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. :D

Post Reply

Return to “Volume 1 (100-199)”