Help! How to do it faster??? (TLE test#3)
Posted by
Dark 3 Jun 2005 21:12
#include <stdio.h>
#include <math.h>
const double PI = 3.141592653;
int n,m,i,i2;
double radius;
double stp[5000],dtp[5000];
double sa,da,mindist,tmp;
double dist(double s1, double d1, double s2, double d2)
{
double x1,y1,x2,y2,z1,z2,s,d;
s = s1*PI/180.0;
d = d1*PI/180.0;
x1 = cos(s)*cos(d);
y1 = cos(s)*sin(d);
z1 = sin(s);
s = s2*PI/180.0;
d = d2*PI/180.0;
x2 = cos(s)*cos(d);
y2 = cos(s)*sin(d);
z2 = sin(s);
double a,b,c,alp;
a = 1;
b = 1;
c = sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) + (z1-z2)*(z1-z2));
alp = acos((a*a + b*b - c*c)/(2*a*b));
return alp;
}
int main()
{
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
scanf("%d %d",&n,&m);
scanf("%lf",&radius);
for (i = 0; i<m; i++)
{
scanf("%lf %lf",&stp[i], &dtp[i]);
}
for (i = 0; i<n; i++)
{
scanf("%lf %lf",&sa, &da);
mindist=9999999;
for (i2 = 0; i2<m; i2++)
{
tmp = dist(sa,da,stp[i2],dtp[i2]);
if (tmp<mindist) mindist = tmp;
}
printf("%.2lf\n",mindist*radius);
}
return 0;
}