Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
给个参考,有种别看#include <iostream> #include <cmath> #include <algorithm> using namespace std; #define EPS 1e-10 #define MAXN 105 double PI=acos(-1.0); struct point { point(double X=0.0,double Y=0.0) { x=X; y=Y; } double x,y; }; point P1[MAXN],P2[MAXN],P3[MAXN]; int n1,n2,n3; int fcmp(double a,double b) { if(a-b>EPS) return 1; else if(b-a>EPS) return -1; else return 0; } struct edge { edge(double ANG=0.0,double preLEN=0.0,double subLEN=0.0) { ang=ANG; preLen=preLEN; subLen=subLEN; } bool operator==(edge &b) { return fcmp(preLen,b.preLen)==0 ; } double ang,preLen,subLen; }; edge E1[MAXN],E2[MAXN]; double getLen(point &ab) { return sqrt(ab.x*ab.x+ab.y*ab.y); } double cross(point &ab,point &bc) { return ab.x*bc.y-ab.y*bc.x; } double dot(point &ab,point &bc) { return ab.x*bc.x+ab.y*bc.y; } double angle(point &ab,point &bc) { double dm=dot(ab,bc)/getLen(ab)/getLen(bc); double dr=acos(dm); double cr=cross(ab,bc); double res=dr*180.0/PI; if(cr<0.0) { if(fcmp(res,90.0)==1) res=180.0+(180.0-res); else res=360.0-res; } return res; } bool isConvex(int i,int j,int k) { int a; if( fcmp(E1[(i-1+n1)%n1].ang + E2[(j-1+n2)%n2].ang , 180.0)==1 ) return false; if( fcmp(E1[(i+k+1+n1)%n1].ang + E2[(j+k+1+n2)%n2].ang , 180.0)==1 ) return false; for( a=(i+k+2)%n1 ; a!=(i-1+n1)%n1 ; a++,a%=n1) { if(fcmp(E1[a].ang,180.0)==1) return false; } for(a=(j+k+2)%n2 ; a!=(j-1+n2)%n2 ;a++,a%=n2) { if(fcmp(E2[a].ang,180.0)==1) return false; } return true; } int check() { int i,j,k,a,s,b; point sa,sb; for(s=0;s<n1;s++) { a=(s-1+n1)%n1; b=(s+1+n1)%n1; sa=point( P1[a].x-P1[s].x , P1[a].y-P1[s].y ); sb=point( P1[b].x-P1[s].x , P1[b].y-P1[s].y ); E1[s]=edge( angle(sb,sa) , getLen(sb) , getLen(sa)); } for(s=0;s<n2;s++) { a=(s-1+n2)%n2; b=(s+1+n2)%n2; sa=point( P2[a].x-P2[s].x , P2[a].y-P2[s].y ); sb=point( P2[b].x-P2[s].x , P2[b].y-P2[s].y ); E2[s]=edge( angle(sa,sb), getLen(sb), getLen(sa)); } for(i=0;i<n1;i++) for(j=0;j<n2;j++) { for(k=0;k<min(n1,n2);k++) { if( !(E1[(i+k)%n1]==E2[(j+k)%n2] )) break; if(k) if( fcmp(E1[(i+k-1)%n1].ang+E2[(j+k-1)%n2].ang,360.0)!=0) break; } k--; if(k>=0) { //printf("check %d %d %d\n",i,j,k); if(isConvex(i,j,k)) return 1; } } return 0; } int main() { //freopen("c:/a.txt","r",stdin); int i; while(scanf("%d",&n1)!=EOF) { for(i=0;i<n1;i++) scanf("%lf%lf",&P1[i].x,&P1[i].y); scanf("%d",&n2); for(i=0;i<n2;i++) { scanf("%lf%lf",&P3[i].x,&P3[i].y); P2[n2-1-i]=P3[i]; } printf("%d\n",check()); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator