Luogu

分析

将每种金属看做一个点 $(a_i, b_i)$，那么两点能配出的所有合金一定在两点构成的线段上。

问题转为给出 $m$ 个点，求一个以这 $m$ 个点为顶点的边数最少的多边形包含 $n$ 个关键点。

如果 $n$ 个点都在 $(x,y)$ 左侧，连一条从 $x$ 到 $y$ 的边权为 $1$ 的边，这样子满足条件的多边形就变成了图上的一个圈。

我们需要求最小圈， Floyd 即可。

注意特判所有点重合和共线的情况，前者输出 $1$，后者输出 $2$。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

const int N=500+10;
const double EPS=1e-10;

struct Point { double x,y; };
typedef Point Vector;
Vector operator -(Point a,Point b) { return (Vector){a.x-b.x,a.y-b.y}; }
bool operator !=(Point a,Point b) { return fabs(a.x-b.x)>EPS||fabs(a.y-b.y)>EPS; }
inline double cross(Vector a,Vector b) { return a.x*b.y-a.y*b.x; }

int n,m;
Point a[N],b[N];
int G[N][N];

inline int judge(Point x,Point y) {
    if (x.x>y.x) swap(x,y);
    for (re 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 (re int i=1;i<=m;++i)
        if (b[i].y<x.y||b[i].y>y.y) return 0;
    return 1;
}

inline int check(Point x,Point y) {
    int p=0,q=0;
    for (re int i=1;i<=m;++i) {
        double t=cross(y-x,b[i]-x);
        if (t>EPS) ++p;
        if (t<-EPS) ++q;
        if (p&&q) return 0; //写在里面，不然容易TLE
    }
    if (!p&&!q&&judge(x,y)) { puts("2"); exit(0); } //特判共线
    if (p) return 1;
    else if (q) return 2;
    else return 3;
}

int main() {
    memset(G,0x3f,sizeof(G));
    scanf("%d%d",&n,&m);
    double junk;
    for (re int i=1;i<=n;++i) scanf("%lf%lf%lf",&a[i].x,&a[i].y,&junk);
    for (re int i=1;i<=m;++i) scanf("%lf%lf%lf",&b[i].x,&b[i].y,&junk);
    //特判全部重合
    int f=1;
    for (re int i=1;i<=n;++i) if (a[i]!=a[1]) f=0;
    for (re int i=1;i<=m;++i) if (b[i]!=a[1]) f=0;
    if (f) { puts("1"); return 0; }

    for (re int i=1;i<n;++i)
        for (re int j=i+1;j<=n;++j) {
            int flag=check(a[i],a[j]);
            if (flag==1) G[i][j]=1;
            else if (flag==2) G[j][i]=1;
            else if (flag==3) G[i][j]=G[j][i]=1;
        }
    for (re int k=1;k<=n;++k)
        for (re int i=1;i<=n;++i)
            for (re int j=1;j<=n;++j)
                G[i][j]=min(G[i][j],G[i][k]+G[k][j]);
    int ans=2e9;
    for (re int i=1;i<=n;++i) ans=min(ans,G[i][i]);
    if (ans>=0x3f3f3f3f||ans<=2) puts("-1");
    else printf("%d\n",ans);
    return 0;
}