【JSOI2007】bzoj1027 合金

可以发现比重只用考虑两维，因此可以把原料看成平面上的点，若干个原料能合成的区域就是凸包。
这样问题变成了求一个点集$A$的最小子集，使得围成的凸包包含另一个点集$B$的所有点。可以枚举$A$中的边，如果$b$中的所有点都在它左侧就连一条有向边。最后floyd找最小环就是答案。

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const double eps=1e-10;
const int maxn=510,oo=0x3f3f3f3f;
int cmp(double x)
{if (x>eps) return 1;if (fabs(x)<=eps) return 0;return -1;
}
struct Vector
{double x,y;void rd(){scanf("%lf%lf%*lf",&x,&y);}Vector operator + (const Vector &v) const{return (Vector){x+v.x,y+v.y};}Vector operator - (const Vector &v) const{return (Vector){x-v.x,y-v.y};}
}a[maxn],b[maxn];
typedef Vector Point;
double dot(Vector v,Vector u)
{return v.x*u.x+v.y*u.y;
}
double cross(Vector v,Vector u)
{return v.x*u.y-v.y*u.x;
}
struct Segment
{Point a,b;
};
int m,n,dis[maxn][maxn];
int check(Segment s)
{int x;for (int i=1;i<=n;i++){x=cmp(cross(s.b-s.a,b[i]-s.a));if (x==1||(x==0&&cmp(dot(b[i]-s.a,b[i]-s.b))==1))return 0;}return 1;
}
int main()
{int ans=oo;scanf("%d%d",&m,&n);for (int i=1;i<=m;i++) a[i].rd();for (int i=1;i<=n;i++) b[i].rd();for (int i=1;i<=m;i++)for (int j=1;j<=m;j++)dis[i][j]=check((Segment){a[i],a[j]})?1:oo;for (int k=1;k<=m;k++)for (int i=1;i<=m;i++)for (int j=1;j<=m;j++)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);for (int i=1;i<=m;i++) ans=min(ans,dis[i][i]);printf("%d\n",ans==oo?-1:ans);
}