题目描述

题解

由于矩形的性质可以发现存在x或y单调

假设是x单调，想象一下有一滴水往x轴正方向落，落到矩形上就分流

用set维护可能的点以及路径长度，扫描线即可

最后要判断能否走到终点，如果跨过了终点的障碍物要把长度（宽度?）设为inf/-inf使得能够走到终点

还要判断横跨整个(x1,y1,x2,y2)的矩形

code

#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define abs(x) ((x)>0?(x):-(x))
#define inf 100000000
#define ll long long
#define file
using namespace std;

struct type{int x1,x2,y;} b[200001];
struct Type{int x;ll s;};
bool operator < (Type a,Type b) {return a.x<b.x;}
int a[200001][4],n,i,j,k,l,X1,Y1,X2,Y2,tot;
set<Type> st;
set<Type> :: iterator I;
ll ans,s1,s2,x1,x2;

void swap(int &x,int &y) {int z=x;x=y;y=z;}
bool cmp(type a,type b) {return a.y<b.y;}
void work()
{
	tot=0;
	fo(i,1,n)
	if (Y1<a[i][1] && a[i][1]<Y2)
	{
		b[++tot]={a[i][0],a[i][2],a[i][1]};
		if (a[i][3]>Y2) {if (a[i][2]<X2) b[tot].x1=0; else b[tot].x2=inf;}
	}
	else
	if (a[i][1]<Y1 && Y2<a[i][3] && X1<a[i][0] && a[i][2]<X2)
	return;
	if (!tot) ans=min(ans,abs(X2-X1)+abs(Y2-Y1));
	sort(b+1,b+tot+1,cmp);
	
	st.clear();st.insert({X1,0});
	fo(i,1,tot)
	{
		I=st.lower_bound({b[i].x1,0});s1=s2=9223372036854775807ll;
		while (I!=st.end() && (*I).x<=b[i].x2)
		{
			s1=min(s1,(*I).s+(*I).x-b[i].x1);s2=min(s2,(*I).s+b[i].x2-(*I).x);
			st.erase(I);
			I=st.lower_bound({b[i].x1,0});
		}
		if (s1<9223372036854775807ll) st.insert({b[i].x1,s1});
		if (s2<9223372036854775807ll) st.insert({b[i].x2,s2});
	}
	
	x1=0;x2=inf;
	fo(i,1,n) if (a[i][1]<Y2 && Y2<a[i][3]) {if (a[i][2]<X2) x1=max(x1,a[i][2]); if (X2<a[i][0]) x2=min(x2,a[i][0]);}
	for (I=st.begin(); I!=st.end(); ++I)
	if (x1<=(*I).x && (*I).x<=x2)
	ans=min(ans,(*I).s+abs((*I).x-X2)+(Y2-Y1));
}

int main()
{
	freopen("travel.in","r",stdin);
	#ifdef file
	freopen("travel.out","w",stdout);
	#endif
	
	scanf("%d%d%d%d%d",&n,&X1,&Y1,&X2,&Y2);
	fo(i,1,n) scanf("%d%d%d%d",&a[i][0],&a[i][1],&a[i][2],&a[i][3]);
	if (X1>X2)
	{
		X1=inf-X1,X2=inf-X2;
		fo(i,1,n) a[i][0]=inf-a[i][0],a[i][2]=inf-a[i][2],swap(a[i][0],a[i][2]);
	}
	if (Y1>Y2)
	{
		Y1=inf-Y1,Y2=inf-Y2;
		fo(i,1,n) a[i][1]=inf-a[i][1],a[i][3]=inf-a[i][3],swap(a[i][1],a[i][3]);
	}
	
	ans=9223372036854775807ll;
	work();
	swap(X1,Y1),swap(X2,Y2);
	fo(i,1,n) swap(a[i][0],a[i][1]),swap(a[i][2],a[i][3]);
	work();
	
	printf("%lld\n",ans);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}

6701. 旅行(travel)

原文：https://www.cnblogs.com/gmh77/p/13060981.html