JSOI2007 合金

题意

\(~~~~\) 给出 \((n+m)\) 个三维点，满足坐标和为 \(1\) 。要求从前 \(n\) 个点中选最少的围成一个多边形，使得后 \(m\) 个多边形均在该多边形内部或边上。求最少选择的数量。

\(~~~~\) \(1\leq n,m\leq 500\).

废话

\(~~~~\) 考场上用 \(20\min\) 胡出来了跟讨论区这一篇完全一样的东西，但甚至没打出来。

题解

\(~~~~\) 首先由于这些点的坐标和为 \(1\) ，那么它们都在同一平面内，因此把它们都改为这一平面上的二维点。（事实上保留前两维即可原因同上，如果数据强一点可能这样还会掉精度）

\(~~~~\) 考虑什么样的点是可以选的，我们发现如果两个点它们之间的连线使得所有目标点都在这条线段的同侧或之上，那么这样的两个点之间可以选来作为最终多边形的一条边。

\(~~~~\) 考虑最后我们要求的多边形事实上就是选择最少得边使其成环，且边满足上述条件，故通过上面的条件建图然后跑出最小环即可。数据范围不大，故可以使用 Floyd

代码

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct Point{
	double x,y,ang;
	Point(){}
	Point(double X,double Y){x=X,y=Y;}
	Point operator +(const Point ano){return Point(x+ano.x,y+ano.y);}
	Point operator -(const Point ano){return Point(x-ano.x,y-ano.y);}
	Point operator *(const double k) {return Point(x*k,y*k);}
	double operator *(const Point ano){return x*ano.x+y*ano.y;}
	double operator ^(const Point ano){return x*ano.y-y*ano.x;}
}P1[505],P2[505]; 
const double EPS=1e-5;
double Dis(Point a,Point b){return sqrt((a.y-b.y)*(a.y-b.y)+(a.x-b.x)*(a.x-b.x));}
double GetDis(double x,double y,double z){return sqrt((x+y-1)*(x+y-1)/2+z*z);}
double Fabs(double x){return x>=EPS?x:-x;}
double Sign(double x)
{
	if(Fabs(x)<=EPS) return 0;
	else return Fabs(x)/x;
}
bool cmp(Point x,Point y){return x.ang!=y.ang?x.ang<y.ang:Dis(x,P1[1])<Dis(y,P1[1]);}
int n,m,Sta[505],Top;
int dis[505][505];
bool CanLink(Point A,Point B)
{
	for(int i=1;i<=m;i++)
	{
		double Tmp;
		Tmp=(P2[i]-A)^(B-A);
		if(Tmp<-EPS) return false;
		if(Fabs(Tmp)<EPS&&(max(A.x,B.x)<P2[i].x||P2[i].x<min(A.x,B.x))) return false;
	}
	return true;
}
int main() {
	double x,y,z;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%lf %lf %lf",&x,&y,&z);
		P1[i].x=GetDis(y,z,x); P1[i].y=GetDis(x,y,z);
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%lf %lf %lf",&x,&y,&z);
		P2[i].x=GetDis(y,z,x); P2[i].y=GetDis(x,y,z);
	}
	if(n==1)
	{
		for(int i=1;i<=m;i++) if(P1[1].x!=P2[i].x||P1[1].y!=P2[i].y) return puts("-1")&0;
		puts("1");
		return 0;
	}
	memset(dis,0x3f,sizeof(dis));
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i==j) continue;
			if(CanLink(P1[i],P1[j])) dis[i][j]=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][k]+dis[k][j],dis[i][j]);
	}
	for(int i=1;i<=n;i++) Ans=min(Ans,dis[i][i]);
	if(Ans==1e8) Ans=-1;
	printf("%d",Ans);
	return 0;
}

\(~~~~\)