自动搬运

查看原文

来自洛谷，原作者为

	cff_0102 & aqua_qaq | 团子群 185800038 | 如果我死了说明我 AFO 了

搬运于2025-08-24 22:56:25，当前版本为作者最后更新于2024-09-30 19:30:16，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

发现 $x,y$ 小于等于 $1000$，可以直接把每个点前的第一个柱子位置和编号存下来。再用一个前缀和数组记录下每两个柱子之间的距离，即代码中的 dis。

要求出两个点之间的距离，可以先找到对应的栅栏的起始点，然后计算它们之间的距离 $d$，即 dis[y]-dis[x]（如果 $y$ 在 $x$ 前面则需要交换这两个点），再分别计算这两个点到栅栏起始点的距离 $dis_1,dis_2$，距离就是 $d-dis_1+dis_2$。

最后只需要输出 $\max(d-dis_1+dis_2,dis_n-(d-dis_1+dis_2))$ 即可。

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
int cald(int xa,int ya,int xb,int yb){
	return abs(xa-xb+ya-yb);
}
struct point{
	int x,y,n;
}pt[200005],lp[1005][1005];
int dis[200005];
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int n,p;cin>>n>>p;
	for(int i=1;i<=p;i++){
		cin>>pt[i].x>>pt[i].y;
		pt[i].n=i;
	}
	pt[0]=pt[p];
	for(int i=1;i<=p;i++){
		int lx=pt[i-1].x,ly=pt[i-1].y,nx=pt[i].x,ny=pt[i].y;
		dis[i]=dis[i-1]+cald(lx,ly,nx,ny);
		if(lx==nx){
			if(ly<ny){
				for(int j=ly;j<ny;j++){
					lp[nx][j].x=lx;
					lp[nx][j].y=ly;
					lp[nx][j].n=i-1;
				}
			}else{
				for(int j=ly;j>ny;j--){
					lp[nx][j].x=lx;
					lp[nx][j].y=ly;
					lp[nx][j].n=i-1;
				}
			}
		}else{
			if(lx<nx){
				for(int j=lx;j<nx;j++){
					lp[j][ny].x=lx;
					lp[j][ny].y=ly;
					lp[j][ny].n=i-1;
				}
			}else{
				for(int j=lx;j>nx;j--){
					lp[j][ny].x=lx;
					lp[j][ny].y=ly;
					lp[j][ny].n=i-1;
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		int xa,xb,ya,yb;cin>>xa>>ya>>xb>>yb;
		int lxa=lp[xa][ya].x,lxb=lp[xb][yb].x,lya=lp[xa][ya].y,lyb=lp[xb][yb].y;
		int lna=lp[xa][ya].n,lnb=lp[xb][yb].n;
		if(lna>lnb){
			swap(xa,xb);
			swap(ya,yb);
			swap(lxa,lxb);
			swap(lya,lyb);
			swap(lna,lnb);
		}
		int dis1=dis[lnb]-dis[lna];
		int disa=cald(xa,ya,lxa,lya);
		int disb=cald(xb,yb,lxb,lyb);
		int ans=abs(dis1-disa+disb);
		cout<<min(ans,dis[p]-ans)<<endl;
	}
	return 0;
}