2297098_ac_125ms_656k.cc

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

#include <stdio.h>
#include <cmath>
#include <algorithm>

using namespace std;

FILE *in, *out;
int p, s[50001];
int n, lowx, lowy;
struct node
{
	int x, y;
}Q[50001];

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

int input()
{
	int i, low = 0;

	in = stdin;
	//in = fopen("triangle.in","r");
	fscanf(in,"%d",&n);
	if(n==-1)
		return 0;
	for(i = 0; i < n; i++)
	{
		fscanf(in,"%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;
		}
	}
	lowx = Q[low].x; lowy = Q[low].y;
	sort(Q,Q+n,cmp);
	return 1;
}

void GRAHAM_SCAN()
{
	int i;

	s[0] = 0;
	i = 1;
	while(i<n-1&&(Q[i].x-lowx)*(Q[i+1].y-lowy)==(Q[i+1].x-lowx)*(Q[i].y-lowy))
		i++;
	s[1] = i++;s[2] = i++;
	p = 2;
	while(i < n)
	{	
		if(i<n-1&&(Q[i].x-lowx)*(Q[i+1].y-lowy)==(Q[i+1].x-lowx)*(Q[i].y-lowy))
		{
			i++;
			continue;
		}
		while((Q[s[p-1]].x-Q[s[p]].x)*(Q[i].y-Q[s[p]].y)>=(Q[i].x-Q[s[p]].x)*(Q[s[p-1]].y-Q[s[p]].y))
			p--;
		s[++p] = i;
		i++;
	}
}

double cal(int a,int b,int c)
{
	double A, B, C, P;

	A = sqrt((Q[s[a]].x-Q[s[b]].x)*(Q[s[a]].x-Q[s[b]].x)+(Q[s[a]].y-Q[s[b]].y)*(Q[s[a]].y-Q[s[b]].y));
	B = sqrt((Q[s[a]].x-Q[s[c]].x)*(Q[s[a]].x-Q[s[c]].x)+(Q[s[a]].y-Q[s[c]].y)*(Q[s[a]].y-Q[s[c]].y));
	C = sqrt((Q[s[c]].x-Q[s[b]].x)*(Q[s[c]].x-Q[s[b]].x)+(Q[s[c]].y-Q[s[b]].y)*(Q[s[c]].y-Q[s[b]].y));
	P = (A+B+C)/2.0;
	return sqrt(P*(P-A)*(P-B)*(P-C));
}

void R_CALIPER()
{
	int i, p1, p2;
	bool mark;
	double max = -1, s1, s2;

	out = stdout;
	//out = fopen("out.txt","w");
	p1 = 1; p2 = 2;
	mark = 1;
	for(i = 0; i < n; i++)
	{
		s1 = cal(i,p1,p2);
		do
		{
			mark = 0;
			while(1)
			{
				s2 = cal(i,(p1+1)%p,p2);
				if(s2 > s1)
				{
					s1 = s2;
					mark = 1;
					p1 = (p1+1)%p;
				}
				else
					break;
			}
			while(1)
			{
				s2 = cal(i,p1,(p2+1)%p);
				if(s2 > s1)
				{
					s1 = s2;
					mark = 1;
					p2 = (p2+1)%p;
				}
				else
					break;
			}
			while(1)
			{
				s2 = cal(i,(p1+1)%p,(p2+1)%p);
				if(s2 > s1)
				{
					s1 = s2;
					mark = 1;
					p2 = (p2+1)%p;
					p1 = (p1+1)%p;
				}
				else
					break;
			}
		}while(mark);
		if(s1 > max)
				max = s1;
	}
	fprintf(out,"%.2lf\n",max);
}

int main()
{
	while(input())
	{
		GRAHAM_SCAN();
		R_CALIPER();
	}
	return 1;
}