比赛 20100423 评测结果 AAAAWAAW
题目名称 可怜的绵羊问题 最终得分 75
用户昵称 .Xmz 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2010-04-23 10:27:58
显示代码纯文本
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>

using namespace std;

struct point
{
	int x,y;
}P[200],D[200];

double f[200][200],ans;
int n,m;

inline int yu(int i)
{
	return i>n ? i-n:i;
}

inline double juli(point p1,point p2)
{
	return sqrt(double(p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}

inline double mianji(point p1,point p2,point p3)
{
	double s1=juli(p1,p2),s2=juli(p2,p3),s3=juli(p3,p1);
	double p=(s1+s2+s3)/2;
	return sqrt(p*(p-s1)*(p-s2)*(p-s3));
}

int chaji(int x1,int y1,int x2,int y2)
{
	return x1*y2-x2*y1;
}

bool trinei(point p,point p1,point p2,point p3)
{
	int t1,t2;
	t1=chaji(p.x-p1.x,p.y-p1.y,p2.x-p1.x,p2.y-p1.y);
	t2=chaji(p.x-p2.x,p.y-p2.y,p3.x-p2.x,p3.y-p2.y);
	if (t1*t2<=0) return false;
	t1=t2;
	t2=chaji(p.x-p3.x,p.y-p3.y,p1.x-p3.x,p1.y-p3.y);
	if (t1*t2<=0) return false;
	return true;
}

bool ok(point p1,point p2,point p3)
{
	for (int i=1;i<=m;i++)
	{
		if (trinei(D[i],p1,p2,p3)) return false;
	}
	return true;
}

bool edgeok(point p1,point p2)
{
	for (int i=1;i<=m;i++)
	{
		if (chaji(D[i].x-p1.x,D[i].y-p1.y,p2.x-p1.x,p2.y-p1.y)==0) return false;
	}
	return true;
}

void init()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	scanf("%d%d",&P[i].x,&P[i].y);
	scanf("%d",&m);
	for (int i=1;i<=m;i++)
	scanf("%d%d",&D[i].x,&D[i].y);	
}

void solve()
{
	for (int S=1;S<=n;S++)
	{
		for (int i=2;i<n;i++)
		{
			for (int j=1;j<i;j++)
			if (ok(P[S],P[yu(S+j)],P[yu(S+i)]))
			if (!f[S][j] || (f[S][j] && edgeok(P[S],P[yu(S+j)])))
			{
				double ss=mianji(P[S],P[yu(S+j)],P[yu(S+i)]);
				if (f[S][i]<f[S][j]+ss)
					f[S][i]=f[S][j]+ss;
			}
		}
	}
	
	for (int S=1;S<=n;S++)
	{
		for (int i=2;i<n;i++)
		if (f[S][i]>ans) ans=f[S][i];
	}
}

int main()
{
	freopen("sheep.in","r",stdin);
	freopen("sheep.out","w",stdout);
	init();
	solve();
	if (ans>=0.00001)
	printf("%0.2lf\n",ans);
	else printf("die\n");
	return 0;
}