knowledgediarybd.com

Your Virtual Knowledge Campus

Computational Geometry Problem Solution

computational-geometry-problem-solutionComputational 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.

Some UVa Computational Geometry Problem Solution :

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:

  1. Introduction of acm ICPC & UVa Online Judge
  2. Programming Sites & Resources
  3. Introduction & Ad Hoc Problems Solution
  4. Data Structures & Libraries problem Solution
  5. UVa Mathematics Problem Solution
  6. String Processing Problem Solution
  7. Graphs Problem Solution
  8. Other Problem Solution
knowledgediarybd.com © 2017
shares