其实这题真的是和http://blog.csdn.net/qq_36797743/article/details/76832740一样的啦
首先，我们知道只有两个属性是有用的，因为只要两个确定了，第三个肯定是一样的啊
我们可以吧a看做x坐标，b看做y坐标，这样就可以吧一个东西抽象成一个点(x,y)
可以证明，两个东西混在一起，他们能组成的状态肯定是他们连线上的点
那么问题就变为我们是否可以找到一个凸包吧用户的点包住啦
因为要是你在里面，那么我们就肯定可以在两条边上选两个点穿过它。。也就是肯定有解。。
于是就和百度之星那题一样了
QAQ要是我早点做这题，就可以装逼啦
但这题比较卡精度一点，要判一下
#include<cstdio>
#include<cstring>
const int N=505;
const int MAX=1<<28;
const double eps=1e-7;
int n,m;
struct Node{
double x,y;};
Node a[N],b[N];//住房 士兵
int f[N][N];
int mymin (int x,int y){
return x<y?x:y;}
bool check (Node a,Node b,Node c)//a是否不在b，c的中间
{if (a.x>b.x+eps&&a.x>c.x+eps) return true;if (a.x<b.x-eps&&a.x<c.x-eps) return true;if (a.y>b.y+eps&&a.y>c.y+eps) return true;if (a.y<b.y-eps&&a.y<c.y-eps) return true;return false;
}
double mu (Node a,Node b,Node c)
{double x1=a.x-c.x,y1=a.y-c.y;double x2=b.x-c.x,y2=b.y-c.y;return x1*y2-x2*y1;
}
int main()
{scanf("%d%d",&m,&n);for (int u=1;u<=m;u++) scanf("%lf%lf%*lf",&b[u].x,&b[u].y);for (int u=1;u<=n;u++) scanf("%lf%lf%*lf",&a[u].x,&a[u].y);for (int u=1;u<=m;u++)for (int i=1;i<=m;i++)f[u][i]=MAX;//printf("%lf\n",mu(b[1],b[3],b[4]));for (int u=1;u<=m;u++){for (int i=1;i<=m;i++){bool tf=true;for (int k=1;k<=n;k++){if (mu(a[k],b[i],b[u])<-eps)//左边{tf=false;}if (mu(a[k],b[i],b[u])<eps&&check(a[k],b[i],b[u])){tf=false;}if (!tf) break;}if (tf) f[u][i]=1;}}for (int u=1;u<=m;u++)for (int i=1;i<=m;i++){if (f[i][u]==MAX) continue;for (int j=1;j<=m;j++)f[i][j]=mymin(f[i][j],f[i][u]+f[u][j]);}int ans=MAX;for (int u=1;u<=m;u++)ans=mymin(ans,f[u][u]);if (ans>m) printf("-1\n");else printf("%d\n",ans);return 0;
}