UVA Problem 109 ( SCUD Busters) :
This problem is UVA uhunt book chapters (Computational Geometry problem) category problem.
link: http://uva.onlinejudge.org/external/1/109.html
Problem Description:
Find each convex hull for each area then select that convex hull whether a Missile falls inside it.Make aggregation of the area among the selected convex hull.
Problem Solution:
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int main()
{
double x1,x2,x3,y1,y2,y3,d,e,h,k,r,g,f,c,a;
char selectA,selectB,selectC;
while(scanf(“%lf %lf %lf %lf %lf %lf”,&x1,&y1,&x2,&y2,&x3,&y3)==6)
{
g=((x1*x1+y1*y1-x3*x3-y3*y3)*(y1-y2)-(x1*x1+y1*y1-x2*x2-y2*y2)*(y1-y3))/(2*(x1-x2)*(y1-y3)-2*(x1-x3)*(y1-y2));
f=((x1*x1+y1*y1-x2*x2-y2*y2)*(x1-x3)-(x1*x1+y1*y1-x3*x3-y3*y3)*(x1-x2))/(2*(x1-x2)*(y1-y3)-2*(x1-x3)*(y1-y2));
c=-(x1*x1+y1*y1+2*g*x1+2*f*y1);
h=-g;
k=-f;
r=sqrt(g*g+f*f-c);
if(h<0)
{
selectA=’+’;
h=-h;
}
else
{
selectA=’-‘;
}
if(h==0)
{
selectA=’+’;
h=-h;
}
if(k<0)
{
selectB=’+’;
k=-k;
}
else selectB=’-‘;
if(k==0)
{
selectB=’+’;
k=-k;
}
printf(“(x %c %.3f)^2 + (y %c %.3f)^2 = %.3f^2\n”,selectA,h,selectB,k,r);
if(g<0)
{
selectA=’-‘;
g=-g;
}
else
{
selectA=’+’;
}
if(g==-0)
{
selectA=’+’;
g=-g;
}
if(f<0)
{
selectB=’-‘;
f=-f;
}
else
{
selectB=’+’;
}
if(f==-0){
selectB=’+’;
f=-f;
}
if(c>0) selectC=’+’;
else
{
selectC=’-‘;
c=-c;
}
printf(“x^2 + y^2 %c %.3fx %c% .3fy %c %.3f = 0\n\n”,selectA,2*g,selectB,2*f,selectC,c);
}
return 0;
}