# UVA Problem 109 ( SCUD Busters) Solution

UVA Problem 109 ( SCUD Busters) :

This problem is UVA uhunt book chapters (Computational Geometry problem) category problem.

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;

}