题意
洛谷P4049
思路
显然知道前两种元素浓度就可以知道第三种，即第三种没有用，我们将前两个浓度\((a,b)\)作为坐标系中的一点
考虑两种合金，它们分别可以拼出它们对应的向量上的所有点，假设两种向量分别为a和b，则它们共同可以拼出
a * x + b * y \((x+y=1)\)
可以看出这些点都在两点的连线上
推广到三个点，即在其中两点的连线的基础上，第三个点向直线连线，形成一个面
由上面可以看出，如果选中了平面上的一些点，它们可以拼出的所有点就是它们所两两连线形成的多边形
问题简化为给定平面上的一些点，求最少的点，使得它们形成的多边形可以将所有目标点包括在内，即求最小点数的凸包
枚举任意两个点i,j，如果它们所形成的线可以使得所有目标点都在其左侧（或右侧，反正要统一），就可以连一条有向边，边权为1，建好图之后跑一遍floyd就可以了
注意特判一下目标点在i,j形成的直线上的情况，由于上面说了两点只能拼出线段上的点，所以如果共线但不在线段上仍然是不行的
Code
#include<bits/stdc++.h>
#define N 505
using namespace std;
const double eps = 1e-8;
int n,m,dis[N][N];
struct Node
{
double a,b,c;
Node(double aa=0.0,double bb=0.0,double cc=0.0) {a=aa;b=bb;c=cc;}
Node operator - (const Node p)const
{
return Node(a-p.a,b-p.b,c-p.c);
}
};
Node ma[N],rq[N];
double xmul(Node a,Node b) {return a.a*b.b-a.b*b.a;}
double pmul(Node a,Node b) {return a.a*b.a+a.b*b.b;}
int main()
{
memset(dis,0x3f,sizeof(dis));
scanf("%d%d",&m,&n);
for(int i=1;i<=m;++i) scanf("%lf%lf%lf",&ma[i].a,&ma[i].b,&ma[i].c);
for(int i=1;i<=n;++i) scanf("%lf%lf%lf",&rq[i].a,&rq[i].b,&rq[i].c);
for(int i=1;i<=m;++i)
for(int j=1;j<=m;++j)
{
bool flag=1;
for(int k=1;k<=n;++k)
{
double xm=xmul(ma[i]-rq[k],ma[j]-rq[k]);
double pm=pmul(ma[i]-rq[k],ma[j]-rq[k]);
if(xm>eps) {flag=0;break;}
else if(fabs(xm)<eps&&pm>eps) {flag=0;break;}
}
if(flag) dis[i][j]=1;
}
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]);
int ans=1e9;
for(int i=1;i<=m;++i) ans=min(ans,dis[i][i]);
if(ans==1e9) cout<<-1<<endl;
else cout<<ans<<endl;
return 0;
}
转载于:https://www.cnblogs.com/Chtholly/p/11544489.html
相关资源：JAVA上百实例源码以及开源项目
