pku2187.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

typedef struct 
{
	int x, y;
	double ang;
} Point;

Point p[50010];

int cmp(const void *a, const void *b)
{
	Point *c = (Point *)a;
	Point *d = (Point *)b;
	if (fabs(c->ang - d->ang) < 1e-6)
	{
		return abs(c->x - p[0].x) - abs(d->x - p[0].x) + abs(c->y - p[0].y) - abs(d->y - p[0].y);
	}
	else if (c->ang > d->ang)
	{
		return 1;
	}
	else
	{
		return -1;
	}
}

int cross(int a, int b, int c)
{
	return (p[b].x - p[a].x) * (p[c].y - p[b].y) - (p[b].y - p[a].y) * (p[c].x - p[b].x);
}

int main()
{
	int i, j;
	int n, tmp, left;
	int stack[500010], top;
	int C;

	while (scanf("%d", &n) != -1 && n != 0)
	{
		for (i = 0; i < n; i++)
		{
			scanf("%d %d", &p[i].x, &p[i].y);
		}
		
		if (n == 1)
		{
			printf("0\n");
			continue;
		}

		if (n == 2)
		{
			C = (p[0].x - p[1].x) * (p[0].x - p[1].x)+ (p[0].y - p[1].y) * (p[0].y - p[1].y);
			printf("%d\n", C);
			continue;
		}
		for (i = 1, left = 0; i < n; i++)
		{
			if (p[i].x < p[left].x)
			{
				left = i;
			}
			else if (p[i].x == p[left].x && p[i].y < p[left].y)
			{
				left = i;
			}
		}

		tmp = p[0].x;
		p[0].x = p[left].x;
		p[left].x = tmp;

		tmp = p[0].y;
		p[0].y = p[left].y;
		p[left].y = tmp;

		for (i = 1; i < n; i++)
		{
			p[i].ang = atan2(p[i].y - p[0].y, p[i].x - p[0].x);
		}

		qsort(p+1, n - 1, sizeof(p[0]), cmp);

		stack[0] = 0;
		for (i = 1; i < n; i++)
		{
			if (fabs(p[1].ang - p[i].ang) > 1e-6)
			{
				stack[1] = i - 1;
				break;
			}
		}
		top = 1;

		for (i = 2; i < n; i++)
		{
			if (i < n - 1 && fabs(p[i].ang - p[i+1].ang) < 1e-6)
			{
				continue;
			}
			while (cross(stack[top-1], stack[top], i) < 0)
			{
				top--;
			}
			top++;
			stack[top] = i;
		}
		top++;

		for (i = 0, C = 0; i < top - 1; i++)
		{
			for (j = i + 1; j < top; j++)
			{
				tmp = (p[stack[i]].x - p[stack[j]].x) * (p[stack[i]].x - p[stack[j]].x) 
					+ (p[stack[i]].y - p[stack[j]].y) * (p[stack[i]].y - p[stack[j]].y);
				if (tmp > C)
				{
					C = tmp;
				}
			}
		}

		printf("%d\n", C);

	}
	return 0;
}