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

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

i need help in c program

Post by moschino » Fri Jun 16, 2006 4:35 pm

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

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sat Jun 17, 2006 11:30 am

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

Post by maxbcr2000 » Sat Oct 07, 2006 9:52 am

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
New poster
Posts: 1
Joined: Wed Jan 10, 2007 8:09 am

190 WA

Post by ABC_FTS » Wed Jan 10, 2007 8:13 am

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
New poster
Posts: 2
Joined: Tue Feb 20, 2007 9:31 pm

190 WA, plz help

Post by Keygen » Thu Feb 22, 2007 6:12 pm

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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Thu Feb 22, 2007 6:27 pm

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
New poster
Posts: 2
Joined: Tue Feb 20, 2007 9:31 pm

Post by Keygen » Thu Feb 22, 2007 7:00 pm

helloneo wrote: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
New poster
Posts: 37
Joined: Tue May 02, 2006 1:01 pm
Contact:

Post by ranban282 » Sat Feb 24, 2007 11:32 am

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

Post by mahfuz05 » Sat Apr 21, 2007 6:48 pm

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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Apr 21, 2007 8:17 pm

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

Post by ranacse05 » Sun Apr 22, 2007 9:38 am

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

Post by ranacse05 » Sun Apr 22, 2007 9:39 am

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
Location: Bangladesh

please help!!P.E in 190....

Post by riisiingsun » Fri May 18, 2007 9:17 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[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]);
	}
}

R!!$!!NG$UN

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

190 CE

Post by linux » Sat Jul 28, 2007 12:54 pm

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.... :P
Solving for fun..

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

190 Circle Through Three Points.

Post by linux » Sat Jul 28, 2007 1:00 pm

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

Post Reply

Return to “Volume 1 (100-199)”