自动搬运

查看原文

来自洛谷，原作者为

	KaisuoShutong 我想说别走 却没有借口。

搬运于2025-08-24 22:13:31，当前版本为作者最后更新于2019-12-06 20:05:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

竟然没有题解，我来一发

对于这种半平面交板子题，关键在于用自己交自己的思想，以及坑点（要输出两个\n）还有就是第38行要把n记下来，因为会改变。

我是 $O(n^2)$ 算法，更快的 $O(n\space logn)$ 请出门左转；

更多的见代码：

#include<stdio.h>
#include<string.h>
#define maxn 100000
struct point{double x,y;
}a[maxn],b[maxn],tmp[maxn];
int N,n;
double Cross(point A,point B,point C)
{
	return (A.x-C.x)*(B.y-C.y)-(B.x-C.x)*(A.y-C.y);
}
double fabs(double x)
{
	return x<0?-x:x;
}
void AddCross(point A,point B,point C,point D)
{
	double c1=fabs(Cross(D,B,A)),c2=fabs(Cross(C,B,A));
	b[++N].x=(c1*C.x+c2*D.x)/(c1+c2),b[N].y=(c1*C.y+c2*D.y)/(c1+c2);
}
void Cut(point A,point B)
{
	N=0,a[n+1]=a[1];
	for(int i=1;i<=n;i++)
		if(Cross(a[i],B,A)>=0)
		{
			b[++N]=a[i];
			if(Cross(a[i+1],B,A)<0) AddCross(A,B,a[i],a[i+1]);
		}
		else if(Cross(a[i+1],B,A)>0) AddCross(A,B,a[i],a[i+1]);
	for(int i=1;i<=N;i++) a[i]=b[i];
	n=N;
}
int main()
{
	int T=0;
	while(scanf("%d",&n)&&n)
	{
		int m=n;
		for(int i=1;i<=n;i++) scanf("%lf %lf",&a[i].x,&a[i].y),tmp[i]=a[i];
		for(int i=1;i<m;i++) Cut(tmp[i],tmp[i+1]);
		++T;
		Cut(tmp[m],tmp[1]);
		if(n) printf("Room #%d:\nSurveillance is possible.\n\n",T);
		else printf("Room #%d:\nSurveillance is impossible.\n\n",T);
	}
	return 0;
}

可以不开double的 QwQ