## 190 - Circle Through Three Points

Moderator: Board moderators

moschino
New poster
Posts: 1
Joined: Fri Jun 16, 2006 4:21 pm
Location: egypt

### i need help in c program

given the Cartesian coordinates of three points on a plane, will find the equation of the circle through them all. The three points will not be on a straight line.

The solution is to be printed as an equation of the form

and an equation of the form

Each line of input to your program will contain the x and y coordinates of three points, in the order , , , , , . These coordinates will be real numbers separated from each other by one or more spaces.

Your program must print the required equations on two lines using the format given in the sample below. Your computed values for h, k, r, c, d, and e in Equations 1 and 2 above are to be printed with three digits after the decimal point. Plus and minus signs in the equations should be changed as needed to avoid multiple signs before a number. Plus, minus, and equal signs must be separated from the adjacent characters by a single space on each side. No other spaces are to appear in the equations. Print a single blank line after each equation pair.

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

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
Why beat about the bush, simply ask for help on problem 190.

maxbcr2000
New poster
Posts: 3
Joined: Tue Oct 03, 2006 4:59 pm

### 190,I got a CE

I compile my code with Microsoft C++ and Dev C++, there is no error,

#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;

int main(int argc, char *argv[])
{
double x1,y1,x2,y2,x3,y3,ox,oy,r,k1,k2,sum;
while(cin>>x1>>y1>>x2>>y2>>x3>>y3)
{
//先求中垂線：(x1-x2)x+(y1-y2)y=k，並利用(x1,y1)，(x2,y2)之中點求出k，
//中垂線：(x1-x2)x+(y1-y2)y=(x1-x2)*((x1+x2)/2)+(y1-y2)*((y1+y2)/2)
k1=(x1-x2)*((x1+x2)/2)+(y1-y2)*((y1+y2)/2);
k2=(x2-x3)*((x2+x3)/2)+(y2-y3)*((y2+y3)/2);
oy=(((x1-x2)*k2-(x2-x3)*k1))/((y2-y3)*(x1-x2)-(x2-x3)*(y1-y2));
ox=((k1-(y1-y2)*oy))/(x1-x2);
r=sqrt(pow(x1-ox,2)+pow(y1-oy,2));
sum=pow(oy,2)+pow(ox,2)-pow(r,2);
char s1="(x - ", s2=" + (y + ",s3=')',s4=')',s5='+'; //判斷"+"、"-"等符號的各種狀況
int Max=1,Max2=1,Max3=1;
if (ox>0) s1 = '-';
else if (ox<0) {s1 = '+';Max=-1;}
else {char s1="x";s3=NULL;}
if (oy>0) s2= '-';
else if(oy<0) {s2='+';Max2=-1;}
else {char s2=" + y";s4=NULL;}
if (sum<0) {s5='-';Max3=-1;}
std::cout<<std::fixed<<std::setprecision(3)<<s1<<Max*ox<<s3<<"^2";
std::cout<<s2<<Max2*oy<<s4<<"^2 = "<<r<<"^2"<<std::endl;
std::cout<<std::fixed<<std::setprecision(3)<<"x^2 + y^2 "<<s1;
std::cout<<" "<<Max*2*ox<<"x"<<" "<<s2<<" "<<Max2*2*oy<<"y"<<" ";
std::cout<<s5<<" "<<Max3*sum<<" = 0"<<std::endl;

}
system("PAUSE");
return EXIT_SUCCESS;
}

The Report:
05013438_24.c: In function `int main(int, char **)':
05013438_24.c:25: warning: converting NULL to non-pointer type
05013438_24.c:28: warning: converting NULL to non-pointer type
05013438_24.c:30: warning: converting NULL to non-pointer type
05013438_24.c:31: `::fixed' undeclared (first use here)

ABC_FTS
New poster
Posts: 1
Joined: Wed Jan 10, 2007 8:09 am

### 190 WA

I have read this forum and passed all the sample outputs.
And I have carefully checked the algorithm. I think there
may be something related to java.

Thanks all for your great help.

Code: Select all

``````import java.util.*;
import java.lang.*;
import java.io.*;

/**
*
* @author  ABC
*/
class Main {
/** Creates a new instance of Main */
public Main() {
}
{
byte lin[] = new byte ;
int lg = 0, car = -1;
String line = "";

try {
while (lg < 1000) {
while (car == 13) {
}
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
} catch (IOException e) {
return (null);
}

if ((car < 0) && (lg == 0)) return (null);  // eof
return (new String(lin, 0, lg));
}

static void p(double d) {
String s = Double.toString(Math.round(Math.abs(d)*1000)/1000d);
System.out.print(s);
int l = s.length();
int dot = s.indexOf(".");
for (int i=0; i<4-l+dot; i++)
System.out.print("0");
}
public static void main(String[] args) {
String tmp;
StringTokenizer stok;
boolean haha = false;
while ((tmp = ReadLn()) != null) {
if (tmp.length() == 0)
continue;
if (haha) {
System.out.println();
System.out.println();
}
haha = true;
double x1,x2,x3,y1,y2,y3;
stok = new StringTokenizer(tmp);
Double temp = new Double(stok.nextToken());
x1 = temp.doubleValue();
temp = new Double(stok.nextToken());
y1 = temp.doubleValue();
temp = new Double(stok.nextToken());
x2 = temp.doubleValue();
temp = new Double(stok.nextToken());
y2 = temp.doubleValue();
temp = new Double(stok.nextToken());
x3 = temp.doubleValue();
temp = new Double(stok.nextToken());
y3 = temp.doubleValue();
double x = 0;
double y = 0;
if (y2 == y3) {
double t = y1;
y1 = y3;
y3 = t;
t = x1;
x1 = x3;
x3 = t;
}
double x12 = (x1 + x2) / 2d;
double y12 = (y1 + y2) / 2d;
double x23 = (x3 + x2) / 2d;
double y23 = (y3 + y2) / 2d;
if (x1 == x2) {
y = y12;
if (y2 == y3) {
x = x23;
} else {
x = ((y - y23) * (y3 - y2) / (x3 - x2) * (-1d)) + x23;
}
}else if (y1 == y2) {
x = (x1 + x2) / 2d;
if (x2 == x3) {
y = (y2 + y3) / 2d;
} else {
y = ((x - x23) * (-1d) * (x3 - x2) / (y3 - y2)) + y23;
}
}else {
double s12 = (x2 - x1) / (y2 - y1);
double s23 = (x3 - x2) / (y3 - y2);
x = ((y12 - y23) + (s12 * x12 - s23 * x23)) / (s12 - s23);
y = (s12 * (x12 - x)) + y12;
}
double r = Math.sqrt((x - x1) * (x - x1) + (y - y1) * (y - y1));
System.out.print("(x");
if (x > 0)
System.out.print(" - ");
else
System.out.print(" + ");
p(x);
System.out.print(")^2 + (y");
if (y > 0)
System.out.print(" - ");
else
System.out.print(" + ");
p(y);
System.out.print(")^2 = ");
p(r);
System.out.println("^2");
System.out.print("x^2 + y^2 ");
if (x > 0)
System.out.print("- ");
else
System.out.print("+ ");
p(2*x);
System.out.print("x ");
if (y > 0)
System.out.print("- ");
else
System.out.print("+ ");
p(2*y);
System.out.print("y ");
if (r > 0)
System.out.print("- ");
else
System.out.print("+ ");
p(x*x+y*y-r*r);
System.out.print(" = 0");
}
}
}
``````

Keygen
New poster
Posts: 2
Joined: Tue Feb 20, 2007 9:31 pm

### 190 WA, plz help

Hi,

I have read this forum and passed all the sample outputs.

Code: Select all

``````#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>

using namespace std;

char sign(long double x)
{
return (x<=0)?'-':'+';
}

void main()
{
while (!cin.eof())
{
long double ax,ay,bx,by,cx,cy;
cin >> ax >> ay >> bx >> by >> cx >> cy;

long double A1,A2,B1,B2,C1,C2;

A1 = by - ay;
B1 = ax - bx;

A2 = cy - ay;
B2 = ax - cx;

swap(A1,B1);
swap(A2,B2);
A1 = -A1;
A2 = -A2;

C1 = -A1*((ax+bx)/2) -B1*(ay+by)/2;
C2 = -A2*((ax+cx)/2) -B2*(ay+cy)/2;

long double x,y,r;

y = (A1*C2 - A2*C1)/(A2*B1-A1*B2);
x = (B1*C2 - B2*C1)/(B2*A1-B1*A2);

r = sqrt((ax-x)*(ax-x)+(ay-y)*(ay-y));

printf("(x %c %.3f)^2 + (y %c %.3f)^2 = %.3f^2\n",sign(-x),fabs(x),sign(-y),fabs(y),r);
printf("x^2 + y^2 %c %.3fx %c %.3fy %c %.3f = 0\n\n",sign(-2*x),fabs(-2*x),sign(-2*y),fabs(-2*y),sign(x*x+y*y-r*r),fabs(x*x+y*y-r*r));
}
}
``````

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
Why don't you search first..

http://online-judge.uva.es/board/viewtopic.php?p=35401

Keygen
New poster
Posts: 2
Joined: Tue Feb 20, 2007 9:31 pm
helloneo wrote:Why don't you search first..

http://online-judge.uva.es/board/viewtopic.php?p=35401

I saw this post, and I changed output, but had WA also..

ranban282
New poster
Posts: 37
Joined: Tue May 02, 2006 1:01 pm
Contact:
When you are trying to print a long double you should use %Lf instead of %f.

mahfuz05
New poster
Posts: 3
Joined: Fri Mar 30, 2007 6:26 am

### why i got WA

i try all possible input its ok but i got WA.

here is my code:

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

char sign( double x)
{
return (x<=0)?'-':'+';
}
int main()
{
double a,b,c,d,m,n,x,y,r,i,j,k,l,o;
while(scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&m,&n)==6)
{
i=(((2*b-2*d)*(c*c+d*d-m*m-n*n))-((a*a+b*b-c*c-d*d)*(2*d-2*n)));
j=(((2*a-2*c)*(2*d-2*n))-((2*c-2*m)*(2*b-2*d)));
k=(((2*c-2*m)*(a*a+b*b-c*c-d*d))-((2*a-2*c)*(c*c+d*d-m*m-n*n)));
x=(i/j);
y=(k/j);
a=fabs(a);
b=fabs(b);

o=(((fabs(x)-a)*(fabs(x)-a))+((fabs(y)-b)*(fabs(y)-b)));

r=sqrt(o);
l=x*x+y*y-r*r;
if(x==0)
{
printf("x^2 + (y %c %.3lf)^2 = %.3lf^2\n",sign(y),fabs(y),r);
printf("x^2 + y^2 %c %.3lfy %c %.3lf = 0\n\n",sign(2*y),fabs(2*y),sign(l),fabs(l));

}
else if(y==0)
{

printf("(x %c %.3lf)^2 + y^2 = %.3lf^2\n",sign(x),fabs(x),r);
printf("x^2 + y^2 %c %.3lfx %c %.3lf = 0\n\n",sign(2*x),fabs(2*x),sign(l),fabs(l));

}
else
{
printf("(x %c %.3lf)^2 + (y %c %.3lf)^2 = %.3lf^2\n",sign(x),fabs(x),sign(y),fabs(y),r);
printf("x^2 + y^2 %c %.3lfx %c %.3lfy %c %.3lf = 0\n\n",sign(2*x),fabs(2*x),sign(2*y),fabs(2*y),sign(l),fabs(l));
}
}
return 0;
}

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Try the cases.

Input:

Code: Select all

``````56 40 66 76 31 8
44 39 26 23 37 38
18 82 29 41 33 15
0 49 19 56 98 3``````
Output:

Code: Select all

``````(x + 33.686)^2 + (y - 84.302)^2 = 100.031^2
x^2 + y^2 + 67.372x - 168.603y - 1764.717 = 0

(x - 42.830)^2 + (y - 22.191)^2 = 16.849^2
x^2 + y^2 - 85.660x - 44.383y + 2042.957 = 0

(x + 279.295)^2 + (y + 19.738)^2 = 314.221^2
x^2 + y^2 + 558.590x + 39.475y - 20339.607 = 0

(x - 32.340)^2 + (y + 9.494)^2 = 66.838^2
x^2 + y^2 - 64.679x + 18.987y - 3331.372 = 0``````
Hope these help.
Ami ekhono shopno dekhi...
HomePage

ranacse05
New poster
Posts: 37
Joined: Wed Mar 28, 2007 5:08 pm
Location: Rajshahi
Contact:

### Need sample I/O

Please some one give me some sample I/O
I like to solve problems.

ranacse05
New poster
Posts: 37
Joined: Wed Mar 28, 2007 5:08 pm
Location: Rajshahi
Contact:

### Need sample I/O

i tried these
input wrote: 5 5 4 7 16 5
56 40 66 76 31 8
44 39 26 23 37 38
18 82 29 41 33 15
0 49 19 56 98 3
output wrote: (x - 10.500)^2 + (y - 9.000)^2 = 6.801^2
x^2 + y^2 - 21.000x - 18.000y + 145.000 = 0

(x + 33.686)^2 + (y - 84.302)^2 = 100.031^2
x^2 + y^2 + 67.372x - 168.603y - 1764.717 = 0

(x - 42.830)^2 + (y - 22.191)^2 = 16.849^2
x^2 + y^2 - 85.660x - 44.383y + 2042.957 = 0

(x + 279.295)^2 + (y + 19.738)^2 = 314.221^2
x^2 + y^2 + 558.590x + 39.475y - 20339.607 = 0

(x - 32.340)^2 + (y + 9.494)^2 = 66.838^2
x^2 + y^2 - 64.679x + 18.987y - 3331.372 = 0
all the output is ok but still WA????
I like to solve problems.

riisiingsun
New poster
Posts: 4
Joined: Fri May 18, 2007 12:03 pm

will any one please tell me why it is giving P.E?

Code: Select all

``````#include<stdio.h>

int strlen(char str[])
{
int i;
for(i=0;str[i]!=NULL;i++);
return i;
}

void main()
{
int i=0,n,k,j,mxm=0;
char str1,str2;

while(gets(str1[i]))
{
k=strlen(str1[i]);
if(k>mxm)
mxm=k;
i++;

}

for(j=i,n=0;j>=0;j--,n++)
{
for(k=0;str1[j][k]!=NULL;k++)
str2[k][n]=str1[j][k];
while(k!=mxm)
{
str2[k][n]=' ';
k++;
}
}

for(j=0;j<mxm;j++)
{
str2[j][n]=NULL;
printf("%s\n",str2[j]);
}
}

``````
R!!\$!!NG\$UN

linux
Learning poster
Posts: 56
Joined: Sat Jul 01, 2006 12:21 pm
Location: CA-95054
Contact:

### 190 CE

Better you run your program in Unix / Linux that you can find out errors easily. Actually the online-judge runs in Linux means GNU C++ Compiler which differs in some levels.... Solving for fun..

linux
Learning poster
Posts: 56
Joined: Sat Jul 01, 2006 12:21 pm
Location: CA-95054
Contact:

### 190 Circle Through Three Points.

The way I solved the problem:

I got 3 equations from three points:
x^2+y^2+2gx + 2fy+c=0;

Then I just made a general solution using determinants that reached my output. Also checked for positive and negatives to avoid multiple signs. I got accepted. The problem doesn't have an input for output -0.000 or +0.000.
Solving for fun..