本文共 1665 字，大约阅读时间需要 5 分钟。
我们可以把每一种金属拆成一个二维向量，显然第三维可以计算出来，是无关的。
我们只需要考虑前两维的情况，显然可以构成点集所形成的凸包内。
然后我们枚举两两的情况，然后可以发现如果所有的点都在一侧是可以选的。
然后我们在点集中，找到一个有向最小环就可以了。
#include #include #include #include #include #include #include using namespace std;#define F(i,j,k) for (int i=j;i<=k;++i)#define D(i,j,k) for (int i=j;i>=k;--i)#define inf 0x3f3f3f3f#define eps 1e-8#define ll long long#define mp make_pair struct Vector{ double x,y; void print() { printf("Vector - > (%.3f,%.3f)\n",x,y); }}; struct Point{ double x,y; void print() { printf("Point (%.3f,%.3f)\n",x,y); }}; double operator * (Vector a,Vector b){ return a.x*b.y-a.y*b.x;} Vector operator - (Point a,Point b){Vector ret;ret.x=a.x-b.x;ret.y=a.y-b.y;return ret;} double dot(Vector a,Vector b){ return a.x*b.x+a.y*b.y;} Point a[505],b[505]; int n,m,c[505][505]; bool judge(Point x,Point y){ F(i,1,m) { double cro=(x-b[i])*(y-b[i]); if (cro>eps) return 0; if (fabs(cro) eps) return 0; } return 1;} bool SPJ(){ F(i,1,n) if (fabs(a[i].x-a[1].x)>eps||fabs(a[i].y-a[1].y)>eps) return 0; F(i,1,m) if (fabs(b[i].x-a[1].x)>eps||fabs(b[i].y-a[1].y)>eps) return 0; return 1;} int main(){ scanf("%d%d",&n,&m); F(i,1,n) scanf("%lf%lf%*lf",&a[i].x,&a[i].y); F(i,1,m) scanf("%lf%lf%*lf",&b[i].x,&b[i].y); if (!m) return printf("0\n"),0; if (SPJ()) return printf("1\n"),0; memset(c,0x3f,sizeof c); F(i,1,n) F(j,1,n) if (i!=j) if (judge(a[i],a[j])) c[i][j]=1; F(k,1,n) F(i,1,n) F(j,1,n) c[i][j]=min(c[i][k]+c[k][j],c[i][j]); int ans=inf; F(i,1,n) ans=min(ans,c[i][i]); printf("%d\n",ans==inf?-1:ans);}
转载于:https://www.cnblogs.com/SfailSth/p/6686147.html