发现 $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;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int P=2e5+10, W=1e3+10;
int px[P], py[P], idx[W][W];
LL d[P];
int dis(int sx, int sy, int ex, int ey) {return abs(sx-ex)+abs(sy-ey);}
int main ()
{
    int n, p;scanf("%d%d", &n, &p);
    for(int i=1;i<=p;++i)scanf("%d%d", &px[i], &py[i]);
    d[0]=0;
    for(int i=1;i<=p;++i)
    {
        idx[px[i]][py[i]]=i;
        int j=i%p + 1;
        d[i]=d[i-1]+dis(px[i-1], py[i-1], px[i], py[i]);
        if(px[i]==px[j])
        {
            int x=px[i], yl=py[i], yh=py[j];
            if(yl>yh)swap(yl, yh);
            for(int y=yl; y<=yh;++y)idx[x][y]=i;
        }
        else
        {
            int y=py[i], xl=px[i], xh=px[j];
            if(xl>xh)swap(xl, xh);
            for(int x=xl;x<=xh;++x)idx[x][y]=i;
        }
    }
    LL L=d[p]+dis(px[1], py[1], px[p], py[p]);
   
    while(n--)
    {
        int sx, sy, ex, ey;scanf("%d%d%d%d", &sx, &sy, &ex, &ey);
        int sid=idx[sx][sy], eid=idx[ex][ey];
        LL d1=dis(ex, ey, px[eid], py[eid])+d[eid];
        LL d2=dis(sx, sy, px[sid], py[sid])+d[sid];
        LL ans=min( abs(d2-d1), L-abs(d2-d1));
        printf("%lld\n", ans);
    }
    return 0;
}