190 - Circle Through Three Points

[moschino]

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]

Why beat about the bush, simply ask for help on problem 190.

[maxbcr2000]

I compile my code with Microsoft C++ and Dev C++, there is no error,
but I got a CE. PLease help me, thanks.

#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[6]="(x - ", s2[9]=" + (y + ",s3=')',s4=')',s5='+'; //判斷"+"、"-"等符號的各種狀況
int Max=1,Max2=1,Max3=1;
if (ox>0) s1[3] = '-';
else if (ox<0) {s1[3] = '+';Max=-1;}
else {char s1[9]="x";s3=NULL;}
if (oy>0) s2[6]= '-';
else if(oy<0) {s2[6]='+';Max2=-1;}
else {char s2[9]=" + 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[3];
std::cout<<" "<<Max*2*ox<<"x"<<" "<<s2[6]<<" "<<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]

Please help!
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() {
    }
    static String ReadLn()  // utility function to read from stdin
    {
        byte lin[] = new byte [1000];
        int lg = 0, car = -1;
        String line = "";
        
        try {
            while (lg < 1000) {
                car = System.in.read();
                while (car == 13) {
                    car = System.in.read();
                }
                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]

Hi,

I have read this forum and passed all the sample outputs.
I don't know why my solution have WA, please help.

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]

Why don't you search first..

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


Do not create a new thread if there is one already..

[Keygen]

Why don't you search first..

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


Do not create a new thread if there is one already..

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

[ranban282]

When you are trying to print a long double you should use %Lf instead of %f.

[mahfuz05]

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]

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.

[ranacse05]

Please some one give me some sample I/O

[ranacse05]

i tried these

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

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

[riisiingsun]

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[200][200],str2[200][200];

	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]);
	}
}

[linux]

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

[linux]

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.