可怜的牧羊人
题目描述：
阿里是一个老实巴交的牧羊人，他有一块地，这块地周边插着一些树桩，阿里用一根粗绳顺次把这些树桩连接起来，构成一个凸多边形，这个多边形就是他的牧羊场。阿里就是靠自己辛勤的劳动卖羊毛挣钱的。过冬了，今年特别冷，所以羊毛的销量特别好，阿里非常高兴。然而住在附近的一个财主看到阿里的收入十分眼红，他在阿里牧场的某些地方下了毒药，想毒死阿里的绵羊。阿里知道了这件事情，但他知道自己斗不过财主，他只能忍受，他所能做的就是把自己的牧羊场缩小，即挑选一些树桩，用绳子重新把牧羊场按顺序围成，以保证牧羊场里的草没有毒药。阿里不希望自己的牧羊场被分隔开，所以围成牧羊场后任意两段绳子除在树桩点外不能相交。他希望新的牧羊场面积尽可能大。但不知道具体是多少，你能帮他算出来么？
输入格式：
第一行是一个整数\(n\) \((1 \leq n \leq 100)\),表示树桩的数目。接下来又\(n\)行，每行两个整数\(X_i\), \(Y_i\) ( $ |X_i| \leq 10000 $ , $ |Y_i| \leq 10000 $ ) , 按逆时针顺序给出每个树桩所在的坐标，这些树桩顺次连成一个凸多边形（该多边形只是形状是凸的，即某些树桩可能会落在多边形边上）。然后是一个整数\(m\)（\(1 \leq m \leq 100\)），表示财主下毒的地点数，跟着\(m\)行，每行两个整数\(P_i\),\(Q_i\)（\(|Pi| \leq 10000，|Qi| \leq 10000\)），即财主下毒地点的坐标，该坐标点可能落在多边形边上或外面，但财主当然不会笨倒在树桩上下毒。
输出格式：
输出文件只有一行，为重新安排后牧羊场的最大面积，答案保留两位小数。如果不可能为成一个新的牧羊场，则输出“ die ”（不包括引号）。
思路
区间dp
先讲一些问题简化 对于这题，我们可以发现给出的凸多边形外的点是多余的，因此不用考虑，读入的时候直接过滤。 然后为了dp时的效率，我们预处理出哪些边上有毒药。 然后下面是dp:\[f_{i,j} = \max_{k = i + 1}^{j - 1}{\{f_{i,j} + S\Delta P_iP_kP_j\}} (P_iP_j上无毒,\Delta P_iP_kP_j内无毒)\] 判断 \(\Delta P_iP_kP_j\)内无毒的方法是这样的，可以预处理出（过滤凸多边形外点后）每一条边外侧（即顺时针方向上）的点，然后如果三角形内无毒，那么三条边外面的点加起来之和应该为总点数（已过滤凸多边形外的点）。CODE
#include#include #include #include using namespace std;#define MAXN 210struct Point{ int x,y; Point(){} Point(int x,int y):x(x),y(y){} bool operator < (const Point &a) const{ return (x*a.y-y*a.x)>0; } bool operator <= (const Point &a) const{ return (x*a.y-y*a.x)>=0; } bool operator != (const Point &a) const{ return x!=a.x||y!=a.y; }}pos[MAXN],poison[MAXN];int f[MAXN][MAXN],outline[MAXN][MAXN];bool cutted[MAXN][MAXN];int i,j,k,m,n,x,y,ans,cnt,r;bool check(int x,int y){ int tmp; for(int i=2;i<=n+1;i++){ tmp=(pos[i].x-pos[i-1].x)*(y-pos[i-1].y)-(pos[i].y-pos[i-1].y)*(x-pos[i-1].x); if(tmp<=0){ return false; } } return true;}bool check(int a,int b,int c){ Point p1(pos[b].x-pos[a].x,pos[b].y-pos[a].y),p2(poison[c].x-pos[a].x,poison[c].y-pos[a].y); if(p1.x*p2.y-p1.y*p2.x==0) return true; return false;}int getsize(int p1,int p2,int p3){ return (pos[p2].x*pos[p3].y-pos[p2].y*pos[p3].x- pos[p1].x*pos[p3].y+pos[p1].y*pos[p3].x+ pos[p1].x*pos[p2].y-pos[p1].y*pos[p2].x);}int main(){ freopen("sheep.in","r",stdin); freopen("sheep.out","w",stdout); memset(f,0,sizeof(f)); scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%d%d",&pos[i].x,&pos[i].y); pos[i].x+=10000,pos[i].y+=10000; } for(i=1;i<=n;i++) pos[n+i]=pos[i]; cnt=0; scanf("%d",&m); for(i=1;i<=m;i++){ scanf("%d%d",&x,&y); x+=10000,y+=10000; if(check(x,y)){ poison[++cnt]=Point(x,y); } } m=cnt; for(i=1;i<=2*n;i++){ for(j=1;j<=2*n;j++){ for(k=1;k<=m;k++){ if(check(i,j,k)==true&&pos[i]!=poison[k]&&pos[j]!=poison[k]) { cutted[i][j]=true; } if(Point(poison[k].x-pos[i].x,poison[k].y-pos[i].y)<=Point(pos[j].x-pos[i].x,pos[j].y-pos[i].y)) outline[i][j]++; } } } ans=0; for(i=3;i<=n+1;i++){ for(j=1;j+i-1<=2*n;j++){ r=j+i-1; for(k=j+1;k<=r-1;k++){ if(outline[j][k]+outline[k][r]+outline[r][j]==m&&(!cutted[j][k])){ f[j][r]=max(f[j][r],f[j][k]+getsize(j,k,r)); } } ans=max(ans,f[j][r]); } } if(ans==0){ printf("die\n"); }else{ printf("%.2f\n",0.5*ans); } return 0;}/*4 //树桩数2 2-2 2-2 -22 -22 //投毒点数0 01 1*/