【计算几何】【分类讨论】Gym - 101243I

题意：给你一个n个点的凸包，让你切一刀，使得它变成一个m边形和一个K边形，问你切的这一刀最短是多少。

如果m+K==n+4，那么一定切在两条边上，但是由于两个线段间的最短距离，至少会经过一条线段的一个端点，于是可以枚举其中一条边，然后算出另一条边，然后枚举4个端点到对面线段的距离，取最小值即可。

如果m+K==n+3，那么一定切在一个点和一个边上，可以枚举那个点，算出顺时针和逆时针方向切到的那条边是谁，然后更新答案。

如果m+K==n+2，那么一定切在两个点上，可以枚举其中一个点，算出顺时针和逆时针方向切到的另外一个点是谁，然后更新答案。

其他情况无解。

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

double ans=99999999999999.0;

struct Point{

	int x,y;

	Point(const int &x,const int &y){

		this->x=x;

		this->y=y;

	}

	Point(){}

	double Length(){

		return sqrt((double)x*(double)x+(double)y*(double)y);

	}

	void read(){

		scanf("%d%d",&x,&y);

	}

}p[105];

typedef Point Vector;

Vector operator - (const Point &a,const Point &b){

	return Vector(a.x-b.x,a.y-b.y);

}

int Dot(const Vector &a,const Vector &b){

	return a.x*b.x+a.y*b.y;

}

int Cross(const Vector &a,const Vector &b){

	return a.x*b.y-a.y*b.x;

}

int n,m,K;

double DisToSegment(Point P,Point A,Point B)

{

	Vector v1=B-A,v2=P-A,v3=P-B;

	if(Dot(v1,v2)<=0) return v2.Length();

	else if(Dot(v1,v3)>0) return v3.Length();

	else return fabs((double)Cross(v1,v2))/v1.Length();

}

double Min(double a,double b,double c,double d,double e){

	return min(a,min(b,min(c,min(d,e))));

}

//double Min(double a,double b,double c){

//	return min(a,min(b,c));

//}

int main(){

	freopen("input.txt","r",stdin);

	freopen("output.txt","w",stdout);

	scanf("%d%d%d",&n,&m,&K);

	for(int i=0;i<n;++i){

		p[i].read();

	}

	if(m+K==n+4){

		if(m==3 || m==n+1){

			puts("0.000");

			return 0;

		}

		for(int i=0;i<n;++i){

			int j=(i+m-2)%n;

			ans=Min(ans,DisToSegment(p[i],p[j],p[(j+1)%n]),

			DisToSegment(p[(i+1)%n],p[j],p[(j+1)%n]),

			DisToSegment(p[j],p[i],p[(i+1)%n]),

			DisToSegment(p[(j+1)%n],p[i],p[(i+1)%n]));

		}

		printf("%.3lf\n",ans);

	}

	else if(m+K==n+3){

		for(int i=0;i<n;++i){

			int j=(i+m-2)%n;

			ans=min(ans,DisToSegment(p[i],p[j],p[(j+1)%n]));

			j=(i-(m-2)+n)%n;

			ans=min(ans,DisToSegment(p[i],p[j],p[(j-1+n)%n]));

		}

		printf("%.3lf\n",ans);

	}

	else if(m+K==n+2){

		for(int i=0;i<n;++i){

			int j=(i+m-1)%n;

			ans=min(ans,(p[i]-p[j]).Length());

			j=(i-(m-1)+n)%n;

			ans=min(ans,(p[i]-p[j]).Length());

		}

		printf("%.3lf\n",ans);

	}

	else{

		puts("-1");

	}

	return 0;

}

巴特西

【计算几何】【分类讨论】Gym - 101243I - Land Division

最新文章

热门文章