自动搬运

查看原文

来自洛谷，原作者为

	SuperJvRuo **

搬运于2025-08-24 21:38:53，当前版本为作者最后更新于2018-04-29 10:33:31，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

第一问

物理题，一个点射出的光线只能射到一个点上，由于光路可逆，所以反过来的点也只有一个。因此答案为$n\div2$。

第二问

模拟题，可以模拟出所有的光线得到匹配。先走一遍路记录边上所有的整点坐标。将图逆时针旋转$45\degree$使得正方向与光线平行，按照坐标排序。先以$x$为第一关键字，$y$为第二关键字排序，求出竖直光线；再以$y$为第一关键字，$x$为第二关键字排序，求出竖直光线。

最后在图上走路即可。

#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>

const int MAX=1e6;

struct point
{
	int x,y,ver,num;
};

bool cmp1(point a,point b)
{
	return a.x!=b.x?a.x<b.x:a.y<b.y;//按旋转后的横坐标排序 
}

bool cmp2(point a,point b)
{
	return a.y!=b.y?a.y<b.y:a.x<b.x;//按旋转后的纵坐标排序 
}

int len[MAX];
int next[MAX][2];
point side[MAX];//边上的点 
int n,m,akt,a,b,c,p;

void make_next(int wh)
{
	std::sort(side,side+n,wh?cmp2:cmp1);
	akt=(-1);
	for(int i=0;i<n;++i)
	{
		if ((side[i].ver>=0)&&((side[i].ver&1)!=wh))
		//发现这个点是顶点 凸的方向与扫的方向不同 
		{
			next[side[i].num][wh]=(-side[i].ver/2-1);//便于输出的一个处理 
			continue;//跳过 
		}
		if (akt<0)
		{
			akt=i;
		}
		else
		{	//可以射过光线，配对 
			next[side[akt].num][wh]=side[i].num;
			next[side[i].num][wh]=side[akt].num;
			akt=(-1);
		}
	}
}

void insert()
{
	side[n].x=a-b;//相当于把图形逆时针旋转了45° 
	side[n].y=a+b;
	side[n].ver=(-1);
	side[n].num=n;
	n++;
}

void find(int fr)
{
	p=fr;
	akt=((next[fr][0]>=0)?0:1);
	while(next[p][akt]>=0)//直到找到一个顶点 
	{
		p=next[p][akt];
		akt^=1;//横竖交替走路 
	}
	p=(next[p][akt]*=(-1));
}

int pp(int k)
{
	return k>=0?k:(m-1);
}

int main()
{
	scanf("%d",&m);
	printf("%d\n",m>>1);
	for(int i=0;i<m;++i)
	{
		scanf("%d %d",&a,&b);
		len[i]=a+b;
	}
	c=len[m-1];
	for(int i=m-1;i>=1;--i)
	{
		len[i]-=len[i-1];
	}
	len[0]-=c;//预处理每条边的长度和方向 
	a=0;
	b=0;
	for(int i=0;i<m;++i)//走路 
	{
		if (i%2)//横向的边 
		{
			if (len[i]>0)//往正方向走路 
			{
				for(int j=0;j<len[i];++j)
				{
					insert();//把点加进去 
					a++;
				}
				side[n-len[i]].ver=((len[pp(i-1)]>0)?(2*i+1):(2*i));
				//根据走路方向加上这个1，表示旋转后这个点向左或右凸出 
				//否则即为向上或下凸 
			}
			else//往负方向走路 
			{
				for(int j=0;j<-len[i];++j)
				{
					insert();
					a--;
				}
				side[n+len[i]].ver=((len[pp(i-1)]<0)?(2*i+1):(2*i));
			}
		}
		else//纵向的边 
		{
			if (len[i]>0)//往正方向走路
			{
				for(int j=0;j<len[i];++j)
				{
					insert();
					b++;
				}
				side[n-len[i]].ver=((len[pp(i-1)]>0)?(2*i+1):(2*i));
			}
			else//往负方向走路 
			{
				for(int j=0;j<-len[i];++j)
				{
					insert();
					b--;
				}
				side[n+len[i]].ver=((len[pp(i-1)]<0)?(2*i+1):(2*i));
			}
		}
	}
	//连光线 
	make_next(0);
	make_next(1);
	for(int i=0;i<n;++i)
	{
		if ((next[i][0]<0)||(next[i][1]<0))//有一个小于0，是顶点 
		{
			find(i);//找到和它唯一对应的顶点 
			printf("%d %d\n",pp(((next[i][0]<0)?(next[i][0]*(-1)):(next[i][1]*(-1)))-2)+1,pp(p-2)+1);
		}
	}
	return 0;
}