Description
有一个(10^8*10^8)的网格图，一格距离为(100)，第(x)条竖线和第(y)条横线的交点记为((x,y))，有一些点上面有半径为(10)的喷泉（一个圆），一行或者一列至多一个喷泉，现在一个人要从((x1,y1))走到((x2,y2))，只能沿着网格走，遇到喷泉的话可以沿着边缘走，问最短距离
Solution
一开始看错题以为可以不沿着网格走的我真的是太弱智了。。
因为只能沿着网格走，所以我们肯定只会往一个方向走（不会来回走这样），然后计算一下就会发现。。因为(2pi*frac{1}{4})是小于(10*2)的，所以我们尽量在有喷泉的地方拐弯，以从左下走到右上为例的话，每次拐弯(y)会(+1)，然后我们又要尽量找有喷泉的地方拐弯，所以其实就是相当于找最长的上升序列
如果说是从右上走到左下的话就反过来（或者直接把所有的坐标反转一下再进行同样的操作即可）
一个需要注意的点：如果说最长的上升序列的长度(=min(abs(x1-x2),abs(y1-y2))+1)，也就是说每一行/每一列都有喷泉的话，答案要再加上(frac{1}{4})圆周长，因为最后一个喷泉不能拐弯了而是要绕过去
mark：不要一看到有点像几何之类的就怂==又不一定是难题。。。
mark：贪心什么的。。以及看清楚题目！
代码大概长这个样子
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const double pi=acos(-1);
const int N=2*(1e5)+10,inf=2147483647;
struct F{
int x,y;
void read(){scanf("%d%d",&x,&y);}
friend bool operator < (F x,F y){return x.x<y.x;}
}a[N];
int lis[N],rec[N];
int n,m;
int stx,sty,edx,edy;
double ans;
int Abs(int x){return x<0?-x:x;}
void solve(){
int tmp,len=0;
memset(rec,-1,sizeof(rec));
for (int i=1;i<=lis[0];++i){
if (rec[len]<lis[i]){
rec[++len]=lis[i];
continue;
}
tmp=lower_bound(rec+1,rec+1+len,lis[i])-rec;
rec[tmp]=lis[i];
}
if (len==(edx-stx+1)||len==Abs(sty-edy)+1) ans=pi*5.0;
else ans=0;
ans+=1LL*((edx-stx)+Abs(sty-edy))*100;
ans+=(pi*5.0-20)*len;
printf("%.15lf
",ans);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
#endif
scanf("%d%d%d%d",&stx,&sty,&edx,&edy);
if (stx>edx) swap(stx,edx),swap(sty,edy);
scanf("%d",&n);
for (int i=1;i<=n;++i) a[i].read();
sort(a+1,a+1+n);
if (sty>edy){
for (int i=1;i<=n;++i) a[i].y=1e8-a[i].y+1;
sty=1e8-sty+1; edy=1e8-edy+1;
}
lis[0]=0;
for (int i=1;i<=n&&a[i].x<=edx;++i)
if (stx<=a[i].x){
if ((sty>=edy&&edy<=a[i].y&&a[i].y<=sty)||(sty<=edy&&sty<=a[i].y&&a[i].y<=edy))
lis[++lis[0]]=a[i].y;
}
solve();
}