2298.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"math.h"
#include"stdio.h"
#include"fstream.h"
//ofstream out("out.txt");
//#define cout out
struct point
{
	double x,y,z;
}p1,p2;
const double pi=3.14159265358979329;
const double eps=1e-8;
inline point operator*(point a,point b)
{
	point c;
	c.x=a.y*b.z-a.z*b.y;
	c.y=a.z*b.x-a.x*b.z;
	c.z=a.x*b.y-a.y*b.x;
	return c;
}
point charge(double theta,double fi)
{
	theta=theta/180*pi;
	fi=fi/180*pi;

	point c;
	c.z=sin(theta);
	c.x=cos(theta)*cos(fi);
	c.y=cos(theta)*sin(fi);
	return c;
}
double dis(point a,point b)
{
	return acos(a.x*b.x+a.y*b.y+a.z*b.z);
}

double answer;

bool input()
{
	double th[2],fi[2];
	double t;char a;
	int i;
	for(i=0;i<2;i++)
	{
		cin>>th[i];
		cin>>a>>t>>a;
		th[i]+=t/60;

		if(a=='S')th[i]*=-1;

		cin>>fi[i];
		cin>>a>>t>>a;
		fi[i]+=t/60;

		if(a=='W')fi[i]=360-fi[i];
	}
	if(th[0]==90||th[1]==90)
	//if(fi[0]==fi[1]&&th[0]==th[1])
	{
		answer=th[0];
		return 1;
	}
	p1=charge(th[0],fi[0]);
	p2=charge(th[1],fi[1]);
	return 0;
}

bool doit()
{
	point b,u;
	double cos_th,sin_th,fi,temp,s1,s2,s,max_z;

	b=p1*p2;
	if(fabs(b.x)<eps&&fabs(b.y)<eps&&fabs(b.z)<eps)
		return 0;

	if(b.z<0)b.z=-b.z,b.x=-b.x,b.y=-b.y;

	if(fabs(b.z-1)<eps)
	{
		answer=0;
		return 1;
	}

	temp=b.x*b.x+b.y*b.y+b.z*b.z;
	cos_th=b.z/sqrt(temp);
	sin_th=sqrt(1-b.z*b.z/temp);

	fi=atan2(b.y,b.x);
	
	u.z=sin_th;
	
	
	u.x=cos_th*cos(fi+pi);
	u.y=cos_th*sin(fi+pi);

	s=dis(p1,p2);
	
	if(fabs(s-pi)<eps)
	{
/*		if(fabs(u.z-p1.z)<eps||fabs(u.z-p2.z)<eps)
		{
			answer=asin(u.z)/pi*180;
			return 1;
		}
		else*/
		while(1);
			return 0;
	}

	s1=dis(p1,u);
	s2=dis(p2,u);
	if(fabs(s1+s2-s)<eps)
		max_z=u.z;
	else
		max_z=p1.z>p2.z?p1.z:p2.z;
	
	answer=asin(max_z)/pi*180;
	
	return 1;
}


int main()
{
//	freopen("out1.txt","W",stdout);

	int t;double f;char c;bool k;
	cin>>t;
	while(t--)
	{
		k=1;
		if(input())k=0;
		
		if(k&&!doit())
			cout<<"undefined\n";

		else 
		{	
			if(answer>0)c='N';
		/*	else if(answer<0&&answer>-0.500001/60)
			{
				c='N';
				answer=0;
			}*/
			else
			{
				answer*=-1;
				c='S';
			}
			
			f=(answer-(long)answer)*60;
			if(f>=59.50001)
			{
				answer++;
				answer-=f/60;
			}
char w[1000];
			sprintf(w,"%d,%.0lf%c\n",(long)(answer),(answer-(long)answer)*60,c);
			if((long)(answer)==0&&(answer-(long)answer)*60==0)c='N';
			sprintf(w,"%d,%.0lf%c\n",(long)(answer),(answer-(long)answer)*60,c);
			cout<<w;
		}
	}
	return 0;
}