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