2236099_wa.cc

北大大牛代码 1240道题的原代码 超级权威

//Graham scan algorithm
//O(nlgn)
# include <stdio.h>
# include <math.h>
# include <algorithm>
# define MAX 1001

using namespace std;

struct node
{
	int x, y;
}Q[MAX];

int n, low;
int lowx, lowy;

bool cmp(struct node a,struct node b)
{
	if(a.x==lowx&&a.y==lowy)
		return 1;
	if(b.x==lowx&&b.y==lowy)
		return 0;
	if((a.x-lowx)*(b.y-lowy)==(b.x-lowx)*(a.y-lowy))
		return (a.x-lowx)*(a.x-lowx)+(a.y-lowy)*(a.y-lowy)<(b.x-lowx)*(b.x-lowx)+(b.y-lowy)*(b.y-lowy);
	return (a.x-lowx)*(b.y-lowy)-(b.x-lowx)*(a.y-lowy) > 0;
}

void input()
{
	int i, j, tmp;

	fscanf(stdin,"%d",&n);
	low = 0;
	for(i = 0; i < n; i++)
	{
		fscanf(stdin,"%d%d",&Q[i].x,&Q[i].y);
		if(i)
		{
			if(Q[i].y < Q[low].y||(Q[i].y == Q[low].y&&Q[i].x<Q[low].x))
				low = i;
		}
	}
	if(n<6)
	{
		fprintf(stdout,"NO\n");
		return ;
	}
	lowx = Q[low].x; lowy = Q[low].y;
	sort(Q,Q+n,cmp);
	for(i = 0; ; i++)
	{
		j = i+2;tmp = 0;
		if(j>n)
		{
			fprintf(stdout,"NO\n");
			return ;
		}
		while(j<=n&&((Q[j%n].x-Q[i].x)*(Q[j-1].y-Q[i].y)==(Q[j-1].x-Q[i].x)*(Q[j%n].y-Q[i].y)))
			j++,tmp++;
		if(!tmp)
		{
			fprintf(stdout,"NO\n");
			return ;
		}
		i = j-2;
		if(i>=n-1)
			break;
	}
	fprintf(stdout,"YES\n");
}

int main()
{
	int t;

	fscanf(stdin,"%d",&t);
	while(t--)
		input();
	return 1;
}