https://vjudge.net/problem/POJ-3304
//#include <bits/stdc++.h> #include <cmath> #include <iostream> //#include <unordered_map> #define mem(x,y) memset(x,y,sizeof(x)) #define pb push_back #define INF 0x3f3f3f3f #define ll long long #define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; const int N=1e5+9; const double eps = 1e-8; const double inf = 1e20; const double pi = acos(-1.0); int n; int sgn(double x) { if(fabs(x)<eps) return 0; if(x<0) return -1; else return 1; } struct Point { double x,y; Point(){} Point(double _x,double _y) { x=_x; y=_y; } Point operator-(Point &b) const { return Point(x-b.x,y-b.y); } double operator^(const Point &b) const { return x*b.y-y*b.x; } }; struct Line { Point s,e; Line(){} Line(Point _s,Point _e) { s=_s; e=_e; } }L[109]; double dis(Point a,Point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } bool ch(Point p1,Point p2) { if(sgn(dis(p1,p2))==0) return 0; for(int i=1;i<=n;i++) { Point p3=L[i].s; Point p4=L[i].e; Point p=p2-p1; Point pp=p3-p1; Point ppp=p4-p1; if(sgn((p^pp)*(p^ppp))>0) return 0; } return 1; } int main() { FAST_IO; int T; cin>>T; while(T--) { cin>>n; double x1,x2,y1,y2; for(int i=1;i<=n;i++) { cin>>x1>>y1>>x2>>y2; L[i]=Line(Point(x1,y1),Point(x2,y2)); } bool f=0; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(ch(L[i].s,L[j].s)||ch(L[i].e,L[j].e)||ch(L[i].e,L[j].s)||ch(L[i].s,L[j].e)) { f=1; break; } } if(f) break; } if(f) cout<<"Yes!"<<endl; else cout<<"No!"<<endl; } return 0; }
