2312404_wa.cpp

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

# include <stdio.h>
# include <math.h>
# include <algorithm>
# define MAX 100010
using namespace std;

typedef long stack;
struct node
{
	double x, y;
}Q[MAX];

long n, low;
double lowx, lowy;
stack p, s[MAX];

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 GRAHAM_SCAN()
{
	long 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(long a,long b,long c)
{
	long d, t;
	double S = 0, S1 = 0;
	stack q, tmp[MAX];
	double A, B, C, P;

	d = a;
	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;
	S = sqrt(P*(P-A)*(P-B)*(P-C));
	tmp[0] = a++;a%=(p+1);
	tmp[1] = (a==b?++a:a);
	a++;a%=(1+p);
	tmp[2] = (a==b?++a:a);
	a++;
	if(a>=(c+1)%(p+1))
		return S;
	q = 2;
	while(a<=c)
	{
		a%=(1+p);
		if(a==b)
		{
			a++;
			continue;
		}
		t = a+1;
		t %= (p+1);
		while(a<c&&(Q[a].x-Q[d].x)*(Q[t].y-Q[d].y)==(Q[t].x-Q[d].x)*(Q[a].y-Q[d].y))
		{
			a++;
			if(t==b)
			{
				a--;
				break;
			}
			t = a+1;
			t %= (1+p);
			continue;
		}
		while((Q[tmp[q-1]].x-Q[tmp[q]].x)*(Q[a].y-Q[tmp[q]].y)>=(Q[a].x-Q[tmp[q]].x)*(Q[tmp[q-1]].y-Q[tmp[q]].y))
			q--;
		tmp[++q] = a;
		a++;
	}
	if(q<=1)
		return S;
	for(d = 0; d <= q; d++)
		S1 += -0.5*(Q[tmp[d]].x * Q[tmp[(d+1)%(q+1)]].y - Q[tmp[d]].y*Q[tmp[(d+1)%(q+1)]].x);
	if(S1<0)
		S1 *= -1;
	return S-S1;
}

int input()
{
	long i;
	double S, min, tmp;
	long a, b;

	scanf("%ld",&n);
	if(!n)
		return 0;
	low = 0;
	for(i = 0; i < n; i++)
	{
		scanf("%lf%lf",&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);
	GRAHAM_SCAN();
	S = 0;
	for(i = 0; i <= p; i++)
		S += -0.5*(Q[s[i]].x * Q[s[(i+1)%(p+1)]].y - Q[s[i]].y*Q[s[(i+1)%(p+1)]].x);
	if(S<0)
		S *= -1;
	min = S;
	for(i = 0; i <= p; i++)
	{
		a = i-1;b = i+1;
		if(a<0)
			a = p;
		if(b==p+1)
			b = 0;
		if((tmp=S-cal(a,i,b))<min)
			min = tmp;
	}
	printf("%.2lf\n",min);
	return 1;
}

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