| ||||||||||
| 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