- 题面描述
- 某公司加工一种由铁、铝、锡组成的合金。他们的工作很简单。首先进口一些铁铝锡合金原材料，不同种类的原材料中铁铝锡的比重不同。然后，将每种原材料取出一定量，经过融解、混合，得到新的合金。新的合金的铁铝锡比重为用户所需要的比重。 现在，用户给出了n种他们需要的合金，以及每种合金中铁铝锡的比重。公司希望能够订购最少种类的原材料，并且使用这些原材料可以加工出用户需要的所有种类的合金。
- 输入格式
- 第一行两个整数m和n（m, n ≤ 500），分别表示原材料种数和用户需要的合金种数。第2到m + 1行，每行三个实数a, b, c（a, b, c ≥ 0 且 a + b + c = 1），分别表示铁铝锡在一种原材料中所占的比重。第m + 2到m +n + 1行，每行三个实数a, b, c（a, b, c ≥ 0 且 a + b + c = 1），分别表示铁铝锡在一种用户需要的合金中所占的比重。
- 输出格式
- 一个整数，表示最少需要的原材料种数。若无解，则输出–1。
- 题解
- 拿到题目，瞬间懵了，这是个啥？先考虑简化的问题，如果只有一维即\(\{a_i\}\)，对于\(a_x,a_y\)\((a_x\leq a_y)\)能组成的数在\([a_x,a_y]\)中；再考虑二维，不难推广成\((a_{x_1},y_1),(x_2，y_2)\)能组成的点为\((x_1,y_1)(x_2,y_2)\)线段上的点。
- 再看一眼题，我们能惊奇地发现题中表面上是三维的，但最后一维完全由前两维确定\(c=1-a-b?\)，也将是三维上的一个确定平面上的点，也就是说我们只需要考虑二维。
- 再回过头去看二维的情况，当\(3\)个点能够合成的合金是\(3\)个点围成的三角形内。
- 如何理解？对于\(3\)个点\(p_1,p_2,p_3\)，\(p_1p_2,p_2p_3,p_1p_3\)为2个物品能合成的合金，再用这些合成的合金与其它融合为其连线段，故三角形由无数条连线段构成。
- 这个结论能够很容易地推广到n个点合成。
- 我们再将线段加上方向变成向量，当点在该向量顺时针180°内称为该向量右侧，当点在该向量逆时针\(180°\)内称为该向量右侧。
- 通过玩数据，我们不难发现最终能够合成所有目标合金为原合金组成的封闭图形，并能够围住所有目标合金。而进一步，当我们将该封闭图形按顺时针定方向后，所有目标合金均在这些向量右侧。
- 我们对每个向量\((x_1,y_1)(x_2,y_2)\)判断目标点是否均在一侧（左\(/\)右），在左侧\((x_1,y_1)\to (x_2,y_2)\)，在右侧\((x_2，y_2)\to (x_1，y_1)\)，即强制转化为向量右侧，那么如果一个点能通过一些向量回到自己，就一定形成包含所有目标点的封闭图形，那么我们用\(floyd\)找最小环即可。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;const int MAXN=505;const double eps=1e-10;int dis[MAXN][MAXN];int n,m;struct rec{ ???double x,y; ???double operator * (const rec& b) const { ???????return x*b.y-y*b.x; ????} ???rec operator - (const rec& b) const { ???????return (rec){x-b.x,y-b.y}; ???}} a[MAXN],b[MAXN];bool inc(rec x,rec y){ ???if (x.x>y.x) swap(x,y); ???for (int i=1;i<=m;i++){ ???????if (b[i].x<x.x||b[i].x>y.x) return 0; ???} ???if (x.y>y.y) swap(x,y); ???for (int i=1;i<=m;i++){ ???????if (b[i].y<x.y||b[i].y>y.y) return 0; ???} ???return 1;}int jud(rec x,rec y){ ???int cnt1=0,cnt2=0; ???for (int i=1;i<=m;i++){ ???????double t=(x-y)*(b[i]-y); ???????if (t>eps) cnt1++; ???????if (t<-eps) cnt2++; ???????if (cnt1*cnt2>0) return 0; ???} ???if (cnt1==0&&cnt2==0&&inc(x,y)) return printf("2\n"),-1; ???if (cnt1>0) return 1; ???if (cnt2>0) return 2; ???return 3;}bool spj(){ ???for (int i=1;i<=n;i++){ ???????if (fabs(a[i].x-a[1].x)>eps||fabs(a[i].y-a[1].y)>eps) return 0; ???} ???for (int i=1;i<=m;i++){ ???????if (fabs(b[i].x-a[1].x)>eps||fabs(b[i].y-a[1].y)>eps) return 0; ???} ???printf("1\n"); ???return 1;}int main(){ ???scanf("%d%d",&n,&m); ???double tmp; ???for (int i=1;i<=n;i++) scanf("%lf%lf%lf",&a[i].x,&a[i].y,&tmp); ???for (int i=1;i<=m;i++) scanf("%lf%lf%lf",&b[i].x,&b[i].y,&tmp); ???if (spj()) return 0; ???for (int i=1;i<=n;i++){ ???????for (int j=1;j<=n;j++) dis[i][j]=1e8; ???} ???for (int i=1;i<=n;i++){ ???????for (int j=i+1;j<=n;j++){ ???????????int t=jud(a[i],a[j]); ???????????if (t==-1) return 0; ???????????if (t==1) dis[i][j]=1; ???????????if (t==2) dis[j][i]=1; ???????????if (t==3) dis[i][j]=dis[j][i]=1; ???????} ???} ???int ans=1e8; ???for (int k=1;k<=n;k++){ ???????for (int i=1;i<=n;i++){ ???????????for (int j=1;j<=n;j++){ ???????????????dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); ???????????} ???????} ???}// ?for (int i=1;i<=n;i++){// ?????for (int j=1;j<=n;j++) printf("%d ",dis[i][j]);// ?????printf("\n");// ?} ???for (int i=1;i<=n;i++) ans=min(ans,dis[i][i]); ???if (ans==1e8||ans<=2) printf("-1\n"); ???else printf("%d\n",ans); ???return 0;}$bzoj1027-JSOI2007$ 合金 计算几何 最小环
原文地址：https://www.cnblogs.com/shjrd-dlb/p/10793721.html