1410.txt

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

#include"iostream.h"
                                                                                 
                                                                                 
double d[4][2],b[2][2];

inline double cheng(int aa,int bb,int c)
{double x1=d[aa][0]-b[c][0],
	x2=d[bb][0]-b[c][0],
	y1=d[aa][1]-b[c][1],
	y2=d[bb][1]-b[c][1];
return 	x1*y2-x2*y1;
}

inline double cheng1(int c)
{double x1=b[0][0]-d[c][0],
        x2=b[1][0]-d[c][0],
        y1=b[0][1]-d[c][1],
        y2=b[1][1]-d[c][1];
return  x1*y2-x2*y1;
}


inline int in(int i)
{double x2,y2,c,x1,y1;

 y1=d[0][1];y2=d[2][1];
if(y1>y2){c=y1;y1=y2;y2=c;}
 x1=d[0][0];x2=d[2][0];
if(x1>x2){c=x1;x1=x2;x2=c;}

if(b[i][0]<=x2&&b[i][0]>=x1&&b[i][1]<=y2&&b[i][1]>=y1)return 1; 

return 0;
}



int inn(int i)
{double x2,y2,c,x1,y1;
       	y1=b[0][1];y2=b[1][1];
if(y1>y2){c=y1;y1=y2;y2=c;}
 x1=b[0][0];x2=b[1][0];
 if(x1>x2){c=x1;x1=x2;x2=c;}
if(d[i][0]<=x2&&d[i][0]>=x1&&d[i][1]>=y1&&d[i][1]<=y2&&cheng1(i)==0)return 1;
return 0;
}



int main()
{
int t,i,j;
cin>>t;
for(;t>0;t--)
{cin>>b[0][0]>>b[0][1]>>b[1][0]>>b[1][1]>>d[0][0]>>d[0][1]>>d[2][0]>>d[2][1];
	d[1][0]=d[0][0];d[1][1]=d[2][1];
	d[3][0]=d[2][0];d[3][1]=d[0][1];

	if(in(0)||in(1)){cout<<"T"<<endl;continue;}	
	
	for(i=0;i<4;i++)
	{j=(i+1)%4;
	if(inn(i))break;
	if(cheng(i,j,0)*cheng(i,j,1)<0&&cheng1(i)*cheng1(j)<0)break;
	}
	
if(i<4)cout<<"T"<<endl;
	else cout<<"F"<<endl;
}
return 1;
}