首页 > 代码库 > UVA11817 - Tunnelling the Earth

UVA11817 - Tunnelling the Earth

给出经纬度,算球面距和圆弧的弦长


我的做法:


设好三维坐标系,利用投影算出两点坐标


利用余弦定理算出圆弧对应圆心角,再算出球面距


我的代码:


#include<iostream>
#include<map>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const double pi=acos(-1),r=6371009;
double cg(double a)
{
	return a/180*pi;
}
int main()
{
	int t;
	double a,b,c,d,x[2],y[2],z[2];
	scanf("%d",&t);
	while(t--)
	{
		scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
		a=cg(a);b=cg(b);c=cg(c);d=cg(d);
		z[0]=r*sin(a);z[1]=r*sin(c);
		y[0]=r*cos(a)*sin(b);y[1]=r*cos(c)*sin(d);
		x[0]=r*cos(a)*cos(b);x[1]=r*cos(c)*cos(d);
		a=pow(x[0]-x[1],2)+pow(y[0]-y[1],2)+pow(z[0]-z[1],2);
		b=acos(1-a/2/r/r);
		b=r*b;
		a=sqrt(a);
		printf("%.0lf\n",b-a);
	}
}

Time limit: 1.000 seconds

Problem E: Tunnelling the Earth

There are different methods of transporting people fromplace to place: cars, bikes, boats, trains, planes, etc.For very long distances, people generally fly in a plane.But this has the disadvantage that the plane must fly aroundthe curved surface of the earth. A distance travelled wouldbe shorter if the traveller followed a straight line fromone point to the other through a tunnel through the earth.

For example, travelling from Waterloo to Cairo requires adistance of 9293521 metres following the great circle route aroundthe earth, but only 8491188 metres following the straight linethrough the earth.

For this problem, assume that the earth is a perfect sphere withradius of 6371009 metres.

Input Specification

The first line of input contains a single integer, the number of testcases to follow. Each test case is one linecontaining four floating point numbers:the latitude and longitude of the origin of the trip,followed by the latitude and longitude of the destination ofthe trip. All of these measurements are in degrees.Positive numbers indicate North latitude and East longitude,while negative numbers indicate South latitude and West longitude.

Sample Input

1
43.466667 -80.516667 30.058056 31.228889

Output Specification

For each test case, output a line containing a single integer, thedifference in the distance between the two points following the greatcircle route around the surface of the earth and following the straightline through the earth, in metres. Round the difference of thedistances to the nearest integer number of metres.

Output for Sample Input

802333

Ond?ej Lhoták

UVA11817 - Tunnelling the Earth