1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; struct Point{ int x; int y; }P; vector<Point> vb,vb1; int used[100]; bool cmp(Point a,Point b) { if(a.x!=b.x) return a.x<b.x; else return a.y<b.y; } int ccw(Point a,Point b,Point c) { int p = a.x*b.y - a.x*c.y - a.y*b.x + a.y*c.x + b.x*c.y - c.x * b.y; if(p>0) return 1; else return 0; } int main() { int N,a,b; while(cin>>N) { if(N==0) break; vb.clear(); for(int i=0;i<N;i++) { cin>>a>>b; P.x=a; P.y=b; used[i]=0; vb.push_back(P); } fill(used,used+N,0); if(N<=3) { cout<<"No\n"; continue; } sort(vb.begin(),vb.end(),cmp); vb1.clear(); vb1.push_back(vb[0]); used[0]=1; for(int i=0;i<(N-1);i++) { int next; for(int j=1;j<N;j++) { if(used[j]==0) { next=j; break; } } for(int j=1;j<N;j++) { if(used[j]==0 && ccw(vb1[i],vb[next],vb[j])==0) next = j; } vb1.push_back(vb[next]); used[next]=1; } vb1.push_back(vb1[0]); vb1.push_back(vb1[1]); int f=0; for(int i=0;i+2<vb1.size();i++) { if(ccw(vb1[i],vb1[i+1],vb1[i+2])==0) { cout<<"Yes\n"; f=1; break; } } if(f==0)cout<<"No\n"; } return 0; } |