前言

校内模拟考试的其中一题，细节很多，测的时候 WA 了几个点，后来才改对

题面

题目链接 (luogu.org/problem/AT2702)

有一个 $10^8 \times 10^8$ 的网格图，相邻格点间上下左右的距离都是 $100m$ ，格点上面有 $n$ 个圆，每个圆半径为 $10m$ ，同一行或同一列最多只有一个圆。

现在要从 $(x_1,y_1)$ 走到 $(x_2,y_2)$ ，只能沿着网格的边或圆周走，输出最短距离（保留 13 位小数）。

样例

思路

对于圆 $i$，只有 $x_i\in\lbrack min(x_1,x_2),max(x_1,x_2)\rbrack,y_i\in\lbrack min(y_1,y_2),max(y_1,y_2)\rbrack$ 时，才是有用的。

从起点到终点，在不走回头路（例如从左下走到右上，每一步必须向右或者向上）的情况下，走过越多的圆越优（$\frac{20\mathrm\pi}4<20$）。

因为不能走回头路，所以选择的圆中 $y$ 坐标是单调的。因为每行每列没有重复的圆，不难看出，即为求解满足范围内圆坐标的 $LIS$。

为了方便，如果 $y_1$ > $y_2$ ，那么交换起点和终点（使求的坐标单调上升）。

如果起点在终点左边，从左到右枚举每个点，如果该点是有用的，那么将它的坐标加入待求 $LIS$ 的数组中。如果起点在终点右边，那么倒着枚举即可。

然后对该数组求一遍 $LIS$，对于每个圆，可以使总路程减少 $20-5\mathrm\pi$ 米。

注意：如果在序列中点的个数等于起终点的间距（线的条数）（如下图），那么必然有一个点是会被经过半个圆的，总答案需要加上 $5\mathrm\pi$ 。

代码

#include<bits/stdc++.h>
#define pi 3.14159265358979323846264338327950288
using namespace std;
inline long long read(){
	long long ret=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
	while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
long long X1,Y1,X2,Y2;
long long a[200005],c[200005],n=0,m,len,iter;
struct node{
	long long x,y;
};
node tmp[200005];
bool cmp(node a,node b){
	if (X1>X2){
		return a.x>b.x;
	}
	return a.x<b.x;
}
int main(){
	X1=read();Y1=read();X2=read();Y2=read();
	if (Y1>Y2){
		swap(X1,X2);
		swap(Y1,Y2);
	}
	m=read();
	for (long long i=1;i<=m;i++){
		tmp[i].x=read(),tmp[i].y=read();
	}
	sort(tmp+1,tmp+1+m,cmp); 
	for (long long i=1;i<=m;i++){
		if (min(X1,X2)<=tmp[i].x&&tmp[i].x<=max(X1,X2)){
			if (min(Y1,Y2)<=tmp[i].y&&tmp[i].y<=max(Y1,Y2)){
				a[++n]=tmp[i].y;
			}
		}
	}
	c[1]=a[1];
	len=1;
	for (long long i=2;i<=n;i++){
		if (a[i]>c[len]){
			len++,c[len]=a[i];
		}else{
			iter=lower_bound(c+1,c+len,a[i])-c,c[iter]=a[i];
		}
	}
	if (n==0){
		len=0;
	}
	double pre=1.00*(abs(X2-X1)+abs(Y2-Y1));
	double stp=20-pi*5; 
	if(len==min(abs(X2-X1)+1,abs(Y2-Y1)+1)){
		printf("%.13lf\n",pre*100*1.00-len*1.00*stp+pi*5);
	}else{
		printf("%.13lf\n",pre*100*1.00-len*1.00*stp);
	}
	return 0;
}