Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

哈哈1A!碎觉去!(匹村现在是凌晨1點。。。)

Posted by KatrineYang at 2016-08-29 13:27:32 on Problem 1228 and last updated at 2016-08-29 13:28:00
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator