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 |
哈哈1A!碎觉去!(匹村现在是凌晨1點。。。)#include <iostream> #include <stdio.h> #include <cmath> #include <algorithm> using namespace std; const double PI = 3.141592654; int N; double k[1005]; inline int next(int n){ return n%(N-1)+1; } bool gx(int x1, int y1, int x2, int y2, int x3, int y3){ long long int X1 = x1, Y1 = y1, X2 = x2, Y2 = y2, X3 = x3, Y3 = y3; return X1*Y2 + X2*Y3 + X3*Y1 == X1*Y3 + X3*Y2 + X2*Y1; } bool compare(int n1, int n2){ return k[n1] < k[n2]; } double K(int x1, int y1, int x2, int y2){ if(y1==y2 && x2>x1) return 0; if(y1==y2 && x2<x1) return PI; if(x1==x2 && y2>y1) return PI/2; if(x1==x2 && y2<y1) return PI*1.5; double res = atan((y2-y1)*1.0/(x2-x1)); if(x2<x1) res += PI; return res; } int main() { int T; scanf("%d", &T); for(int ii = 0; ii < T; ii++){ scanf("%d", &N); int x[1005], y[1005]; int mnX = 2147483647, mnY = 2147483647, arg = -1; for(int i = 0; i < N; i++){ int X, Y; scanf("%d%d", &X, &Y); if(X < mnX || (X == mnX && Y < mnY)){ mnX = X; mnY = Y; arg = i; } x[i] = X, y[i] = Y; } if(N < 6) { printf("NO\n"); continue; } if(arg != 0){ int temp = x[arg]; x[arg] = x[0]; x[0] = temp; temp = y[arg]; y[arg] = y[0]; y[0] = temp; } //cout << x[0] << y[0] << endl; for(int i = 1; i < N; i++){ k[i] = K(x[0],y[0],x[i],y[i]); } //sort(k+1, k+N); int ord[2016]; for(int i = 1; i < N; i++) ord[i] = i; sort(ord+1, ord+N, compare); //for(int i = 1; i < N; i++) cout << x[ord[i]] << y[ord[i]] << " "; cout << endl; if(k[ord[N-1]]-k[ord[1]]<1e-7) { printf("NO\n"); continue; } int start; if(k[ord[N-1]]-k[ord[1]] < PI+1e-7) start = 1; else{ for(int j = 2; j < N; j++){ if(k[ord[j]]-k[ord[j-1]] > PI-1e-7){ start = j; break; } } } //cout << start << endl; for(int i = N; i <= start+N-2; i++) ord[i] = ord[i%(N-1)]; int mnStart = start, mnEnd = start+N-2; int startDis = abs(x[ord[start]]-x[0]) + abs(y[ord[start]]-y[0]); int endDis = abs(x[ord[start+N-2]]-x[0]) + abs(y[ord[start+N-2]]-y[0]); int startArg = start, endArg = start+N-2; while(abs(k[ord[mnStart]]- k[ord[start]]) < 1e-7){ int tempDis = abs(x[ord[mnStart]]-x[0]) + abs(y[ord[mnStart]]-y[0]); if(tempDis > startDis){ startDis = tempDis; startArg = mnStart; } mnStart++; } mnStart--; if(mnStart == start){ printf("NO\n"); continue; } while(abs(k[ord[mnEnd]]- k[ord[start+N-2]]) < 1e-7){ int tempDis = abs(x[ord[mnEnd]]-x[0]) + abs(y[ord[mnEnd]]-y[0]); if(tempDis > endDis){ endDis = tempDis; endArg = mnEnd; } mnEnd--; } mnEnd++; if(mnEnd == start+N-2){ printf("NO\n"); continue; } //cout << mnStart << mnEnd << endl; if(startArg != mnStart){ int tmp = ord[startArg]; ord[startArg] = ord[mnStart]; ord[mnStart] = tmp; } if(endArg != mnEnd){ int tmp = ord[endArg]; ord[endArg] = ord[mnEnd]; ord[mnEnd] = tmp; } if(mnEnd - mnStart < 2){ printf("NO\n"); continue; } //cout << mnEnd - mnStart << endl; int startP = mnStart; bool ky = 1; while(startP < mnEnd-1){ if(!gx(x[ord[startP]], y[ord[startP]], x[ord[startP+1]], y[ord[startP+1]], x[ord[startP+2]], y[ord[startP+2]])){ ky = 0; break; } while(startP < mnEnd -1 && gx(x[ord[startP]], y[ord[startP]], x[ord[startP+1]], y[ord[startP+1]], x[ord[startP+2]], y[ord[startP+2]])){ startP++; } startP++; } if(ky && !gx(x[ord[mnEnd]], y[ord[mnEnd]], x[ord[mnEnd-1]], y[ord[mnEnd-1]], x[ord[mnEnd-2]], y[ord[mnEnd-2]])){ ky = 0; } if(!ky) printf("NO\n"); else printf("YES\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