给出n个白点和m个黑点.现在你需要选择一些白点把黑点圈起来.每有一个黑点不能被选出的白点组成的凸包包含就需要付出111的代价,每选出一个白点就需要付出20的代价.要求最小化代价之和 n,m<=100
首先选出三个白点的代价小于扔掉一个黑点的代价,那么显然我们要尽量多地圈黑点.对所有白点求一个凸包,此时包含的黑点数目达到最多,但不一定是最优方案,因为也许可以少选一些白点,包含同样数目的黑点.那么就是选出尽量少的白点使得它们包含之前被凸包包含的黑点.这里我脑抽了一下...实际上推到这里和JSOI 合金 已经等价了,建图跑最小环即可.因为是计算几何题,所以往CEOI官网扒了数据测了一发过了才敢往bzoj交
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=105; struct point{ double x,y; point(){} point(double a,double b){x=a;y=b;} void read(){ scanf("%lf%lf",&x,&y); } bool operator <(const point &B)const{ return (x==B.x)?y<B.y:x<B.x; } bool operator ==(const point &B)const{ return x==B.x&&y==B.y; } }P1[maxn],P2[maxn],P3[maxn],stk[maxn];int top=0,cnt=0; point operator +(const point &A,const point &B){ return point(A.x+B.x,A.y+B.y); } point operator -(const point &A,const point &B){ return point(A.x-B.x,A.y-B.y); } double cross(const point &A,const point &B){ return A.x*B.y-A.y*B.x; } void convexhull(point *P,int n){ sort(P+1,P+n+1); stk[top++]=P[1]; for(int i=2;i<=n;++i){ while(top>1&&cross(stk[top-1]-stk[top-2],P[i]-stk[top-2])>=0)top--; stk[top++]=P[i]; } int lim=top; for(int i=n-1;i>=1;--i){ while(top>lim&&cross(stk[top-1]-stk[top-2],P[i]-stk[top-2])>=0)top--; stk[top++]=P[i]; } --top; } bool betw(double x,double a,double b){ return (a<=x&&x<=b)||(b<=x&&x<=a); } bool onseg(point o,point A,point B){ return betw(o.x,A.x,B.x)&&cross(A-o,B-o)==0; } bool inside(point x,point A,point B,point C){ if(x==A||x==B||x==C)return true; if(onseg(x,A,B)||onseg(x,A,C)||onseg(x,B,C))return true; int s1=(cross(B-A,x-A)>0),s2=(cross(C-B,x-B)>0),s3=(cross(A-C,x-C)>0); return s1==s2&&s2==s3; } bool inside(point A){ if(cross(stk[1]-stk[0],A-stk[0])>0)return false; if(cross(stk[top-1]-stk[0],A-stk[0])<0)return false; int l=1,r=top-1; while(l<=r){ int mid=(l+r)>>1; if(cross(stk[mid]-stk[0],A-stk[0])>0)r=mid-1; else l=mid+1; } return inside(A,stk[0],stk[r],stk[r+1]); } int w[105][105]; int main(){ int n,m;scanf("%d%d",&n,&m); for(int i=1;i<=n;++i)P1[i].read(); for(int i=1;i<=m;++i)P2[i].read(); convexhull(P1,n); for(int i=1;i<=m;++i){ if(inside(P2[i]))P3[++cnt]=P2[i]; } if(cnt==0)printf("%d\n",111*m); else{ memset(w,0x3f,sizeof(w)); for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ if(i!=j){ bool flag=true; for(int k=1;k<=cnt;++k){ if(cross(P1[j]-P1[i],P3[k]-P1[i])<0)flag=false; } if(flag)w[i][j]=1; } } } for(int k=1;k<=n;++k){ for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ if(w[i][k]+w[k][j]<w[i][j])w[i][j]=w[i][k]+w[k][j]; } } } int ans=0x3f3f3f3f; for(int i=1;i<=n;++i)if(w[i][i]<ans)ans=w[i][i]; printf("%d\n",20*ans+(m-cnt)*111); } return 0; }转载于:https://www.cnblogs.com/liu-runda/p/7006898.html
相关资源：数据结构—成绩单生成器