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 |
终于AC了,注意是直线与线段相交,因为这个调了一下午#include<iostream> #include<cstdio> #include<cmath> #define x first #define y second using namespace std; const double EPS=1e-8; int n,t; pair<double,double> s[210]; double Max(double a,double b) { if(a>b) return a; else return b; } double Min(double a,double b) { if(a<b) return a; else return b; } bool judge(int a,int b,int c,int d) { if(((s[b].x-s[a].x)*(s[c].y-s[a].y)-(s[b].y-s[a].y)*(s[c].x-s[a].x))*((s[b].x-s[a].x)*(s[d].y-s[a].y)-(s[b].y-s[a].y)*(s[d].x-s[a].x))>EPS) return 0; else return 1; } double dis(int a,int b) { return sqrt((s[a].x-s[b].x)*(s[a].x-s[b].x)+(s[a].y-s[b].y)*(s[a].y-s[b].y)); } bool check(int a,int b) { if(dis(a,b)<EPS) return 0; for(int i=1;i<=n;i++) { if(!judge(a,b,i*2-1,i*2)) return 0; } return 1; } int main() { scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%lf%lf%lf%lf",&s[i*2-1].x,&s[i*2-1].y,&s[i*2].x,&s[i*2].y); } int flag=0; for(int i=1;i<2*n;i++) { for(int j=i+1;j<=2*n;j++) { if(check(i,j)) { flag=1; break; } } if(flag) break; } if(flag) printf("Yes!\n"); else printf("No!\n"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator