# Computational Geometry Problem Solution

Computational Geometry Problem  Solution are less difficult then Graph problem  in UVa  Problem set. Geometry Problem are more important and interesting because most of the Geometry problem are related  to our previous geometric knowledge. Computational Geometry Problem: Points and Lines,  Circles, Triangles (plus Circles),Quadrilaterals, Great-Circle Distance, Other 3D Objects.

Actually most Computational Geometry Problem are easy and can be solved by previous knowledge.  But be careful about time, space and special criteria when solving them.

# UVa: 190 – Circle Through Three Points

```#include <stdio.h>
#include <math.h>
int main(){
float x1,x2,x3,y1,y2,y3,d,e,h,k,r,g,f,c,a;
char ch1,ch2,ch3;
while(scanf("%f %f %f %f %f %f",&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;
a=sqrt(g*g+f*f-c);

if(h>0) ch1='-';
else {ch1='+'; h=-h;}
if(h==0) {ch1='+'; h=-h;}
if(k>0) ch2='-';
else {ch2='+'; k=-k;}
if(k==0) {ch2='+'; k=-k;}

printf("(x %c %.3f)^2 + (y %c %.3f)^2 = %.3f^2\n",ch1,h,ch2,k,a);

if(g>0) ch1='+';
else if(g<0) {ch1='-'; g=-g;}
if(g==-0) {ch1='+'; g=-g;}
if(f>0) ch2='+';
else if(f<0) {ch2='-'; f=-f;}
if(f==-0) {ch2='+'; f=-f;}
if(c>0) ch3='+';
else {ch3='-'; c=-c;}

printf("x^2 + y^2 %c %.3fx %c% .3fy %c %.3f = 0\n\n",ch1,2*g,ch2,2*f,ch3,c);
}

return 0;
}```

# UVa:  378 – Intersecting Lines

```#include <cstdio>
using namespace std;

int main(){
int n;
double x1,y1,x2,y2,x3,y3,x4,y4,m1,m2,n1,n2,x,y,c1,c2;

scanf("%d",&n);
printf("INTERSECTING LINES OUTPUT\n");
while(n--)
{
scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);

m1=y1-y2; n1=-(x1-x2); c1=-x1*m1-y1*n1;
m2=y3-y4; n2=-(x3-x4); c2=-x3*m2-y3*n2;

if(m1*n2-m2*n1==0 && n1*c2-n2*c1==0 && m1*c2-m2*c1==0) printf("LINE\n");
else if(m1*n2-m2*n1==0 && (n1*c2-n2*c1!=0 || m1*c2-m2*c1!=0)) printf("NONE\n");
else
{
x=(n1*c2-n2*c1)/(m1*n2-m2*n1);
y=(m2*c1-m1*c2)/(m1*n2-m2*n1);
printf("POINT %.2lf %.2lf\n",x,y);
}
}
printf("END OF OUTPUT\n");
return 0;
}```

# UVa: 476 – Points in Figures: Rectangles

```#include <stdio.h>
int main(){
int i=0,cout=1,judge=0,j;
double x1,y1,x[10][2],y[10][2];
char r;

while(1)
{
scanf("%c",&r);
if(r=='*') break;
else if(r=='r')
{
scanf("%lf %lf %lf %lf",&x[i][0],&y[i][0],&x[i][1],&y[i][1]);
i++;
}
}

while(scanf("%lf %lf",&x1,&y1)==2)
{

if(x1==9999.9 && y1==9999.9) break;
for(j=0,judge=0; j<i; j++)
{
if(x1>x[j][0] && x1<x[j][1] && y1>y[j][1] && y1<y[j][0] )
{
printf("Point %d is contained in figure %d\n",cout,(j+1));
judge=1;
}
}

if(judge==0 && x1!=9999.9)
printf("Point %d is not contained in any figure\n",cout);

cout++;
}

return 0;
}```

# UVa: 10286 – Trouble with a Pentagon

```#include <stdio.h>
#include <math.h>
#define pi acos(0.0)

int main()
{
double n;

while(scanf("%lf",&n)==1)
{
printf("%.10lf\n",(n*sin(108*pi/90)/sin(63*pi/90)));
}

return 0;
}```

# UVa: 10451 – Ancient Village Sports

```#include <cstdio>
#include <cmath>
#define pi 2*acos(0.0)
using namespace std;

int main()
{
double n,x,y,a,R,r,A1,A2,A;
int i=1;
while(scanf("%lf %lf",&n,&A)==2 && n>2)
{
R=sqrt(2*A/(n*sin(2*pi/n)));
r=sqrt(A/(n*tan(pi/n)));
A1=pi*R*R;
A2=pi*r*r;

printf("Case %d: %.5lf %.5lf\n",i,A1-A,A-A2);
i++;
}

return 0;
}```

## Related Post or You may Like:

Updated: October 15, 2014 — 3:59 pm