纯半平面交+判断是否存在核。。。
View Code
1 /* 2 半平面交+判断是否有核 3 */ 4 #include<stdio.h> 5 #include<string.h> 6 #include<stdlib.h> 7 #include<algorithm> 8 #include<iostream> 9 #include<queue> 10 //#include<map> 11 #include<math.h> 12 using namespace std; 13 typedef long long ll; 14 //typedef __int64 int64; 15 const int maxn = 105; 16 const int inf = 0x7fffffff; 17 const double pi=acos(-1.0); 18 const double eps = 1e-8; 19 struct Point{ 20 double x,y; 21 }; 22 Point point[ maxn ],ans[ maxn ],tt; 23 int num_ans; 24 25 int sig( double d ){ 26 if( d>eps ) return 1; 27 if( d<-eps ) return -1; 28 return 0; 29 } 30 31 double xmult( Point sp,Point ep,Point op ){ 32 return ( sp.x-op.x )*( ep.y-op.y )-( sp.y-op.y )*( ep.x-op.x ); 33 } 34 35 double get_Area( Point pt[],int n ){ 36 double area = 0; 37 pt[ n ] = pt[ 0 ]; 38 tt.x=tt.y=0.0; 39 for( int i=0;i<n;i++ ){ 40 area += xmult( pt[ i ],pt[ i+1 ],tt ); 41 } 42 return area; 43 }//得到某个凸多边形的面积 44 45 void cut( Point tmp[],Point a,Point b,int n ){ 46 int cnt = 0;//统计当前ab一侧能有多少个点 47 for( int i=0;i<num_ans;i++ ){ 48 double s1,s2; 49 s1 = xmult( tmp[ i ],a,b ); 50 s2 = xmult( tmp[ i+1 ],a,b ); 51 int d1,d2; 52 d1 = sig( s1 ),d2 = sig( s2 ); 53 if( d1>=0 ) ans[ cnt++ ] = tmp[ i ]; 54 else if( d1*d2<0 ){ 55 ans[ cnt ].x = (s2*tmp[i].x-s1*tmp[i+1].x)/(s2-s1); 56 ans[ cnt++ ].y = (s2*tmp[i].y-s1*tmp[i+1].x)/(s2-s1); 57 } 58 } 59 num_ans = cnt;//update the num_ans, 60 } 61 62 void solve( int n ){//the num of the ve 63 if( get_Area( point,n )<0 ) 64 reverse( point,point+n );//逆向改变点的顺序 65 point[ n ] = point[ 0 ]; 66 num_ans = n; 67 for( int i=0;i<=n;i++ ) 68 ans[ i ] = point[ i ];//init of the ans 69 for( int i=0;i<n;i++ ){ 70 cut( ans,point[ i ],point[ i+1 ],n ); 71 } 72 if( num_ans==0 ) printf("NO\n"); 73 else printf("YES\n"); 74 return ; 75 } 76 77 int main(){ 78 int ca; 79 scanf("%d",&ca); 80 while( ca-- ){ 81 int n; 82 scanf("%d",&n); 83 for( int i=0;i<n;i++ ) 84 scanf("%lf%lf",&point[ i ].x,&point[ i ].y); 85 tt.x=tt.y=0; 86 solve( n ); 87 } 88 return 0; 89 }