分析：
首先，走1/4圆会缩短路径，但走1/2圆会增长路径。所以肯定希望尽可能多走1/4圆，尽可能不走1/2圆。
很容易看出最长上升子序列的模型：
显然不可能向目标的反方向走，所以每一步永远是向上或向右（假设目标点在出发点右上方）。因此，能走的步数永远是不下降的。然而题目要求每一行每一列最多只有1个圆，所以就成了最长上升子序列问题。
现在考虑不得不走的1/2圆的情况：很显然，当且仅当每一行或每一列都有圆，才会仅走一次1/2圆。证明很简单，为了方便起见，现在不妨设n<m（行数<列数），一开始，每次走的圆都是走的左上侧，然而终点在右侧，所以如果每一行都有圆，又根据我们不走反向的原则，就一定得走一个半圆，使得状态从左上侧变为右下侧。
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define SF scanf #define PF printf #define MAXN 200010 #define x first #define y second using namespace std; typedef long long ll; pair<int,int> p[MAXN]; const double Pi=acos(-1); int xl,yl,xr,yr; int fx,fy; int n; int st[MAXN]; int main(){
SF("%d%d%d%d",&xl,&yl,&xr,&yr);if(xl>xr)fx=-1;elsefx=1;if(yl>yr)fy=-1;elsefy=1;xl*=fx,xr*=fx,yl*=fy,yr*=fy;SF("%d",&n);for(int i=1;i<=n;i++){
SF("%d%d",&p[i].x,&p[i].y);p[i].x*=fx;p[i].y*=fy;if(p[i].x<xl||p[i].x>xr||p[i].y<yl||p[i].y>yr){
n--;i--;continue;}}sort(p+1,p+1+n);int top=0;for(int i=1;i<=n;i++){
if(top==0||st[top]<p[i].y)st[++top]=p[i].y;else{
int pos=lower_bound(st+1,st+1+top,p[i].y)-st;st[pos]=p[i].y; }}double ans=(xr-xl)*100.0+(yr-yl)*100.0;ans=ans+(double)top*(Pi*5.0-20.0);if(top==min(xr-xl+1,yr-yl+1))ans+=Pi*5;PF("%.11lf",ans); }