| ||||||||||
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 <cstdio> #include <cstring> #include <vector> #include <cmath> using namespace std; #define rc 1e-8 int N; template<typename T> class Point{ public: T x; T y; Point(){}; bool operator == (const Point &p)const{ if(abs(x-p.x)<rc&&abs(y-p.y)<rc){ return true; } return false; } }; template<typename T> class Line{ public: Line(){} void set(T l,T u,T r,T d){ lu.x=l;lu.y=u; rd.x=r;rd.y=d; } Point<T> lu,rd; }; vector<Line<double> > v(105); template<typename T> T mult(Point<T> &sp,Point<T> &ep,Point<T> &op){ return (op.x-sp.x)*(sp.y-ep.y)-(op.y-sp.y)*(sp.x-ep.x); } template<typename T> bool cross(Point<T> &p1,Point<T> &p2){ if(p1==p2) return false; for(int i=0;i<N;i++){ if(mult(p1,p2,v[i].lu)*mult(p1,p2,v[i].rd)>rc){ return false; } } return true; } bool judge(int i,int j){ if(cross(v[i].lu,v[j].lu)) return true; if(cross(v[i].lu,v[j].rd)) return true; if(cross(v[i].rd,v[j].lu)) return true; if(cross(v[i].rd,v[j].rd)) return true; return false; } bool solve(){ if(N<3) return true; for(int i=0;i<N-1;i++) for(int j=i+1;j<N;j++) if(judge(i,j)){ return true; } return false; } int main() { int T; double l,d,r,u; int i; scanf("%d",&T); while(T--){ scanf("%d",&N); for(i=0;i<N;i++){ scanf("%lf%lf%lf%lf",&l,&u,&r,&d); v[i].set(l,u,r,d); } if(solve()){ puts("Yes!"); }else{ puts("No!"); } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator