AtCoder Grand Contest 019 C-Fountain Walk欲張り+dp

に言及
無限大のメッシュ図があり、(x 1,y 1)から(x 2,y 2)まで歩くことが要求される.n個の格子点に半径0.1個の単位長さの噴水があり、噴水を通るときは円周に沿って歩かなければならない.最短を尋ねる.n<=20000,x 1,y 1,x 2,y 2<=1 e 8は、同じ行または同じ列に2つの噴水がないことを満たす.
ぶんせき
噴水を歩くと、曲がると経路が短くなり、まっすぐ行くと経路が長くなることがわかります.欲張って考えると、できるだけ曲がって歩く噴水が多ければ多いほどいいに違いない.噴水の半径があまりにも小さいので、迂回できません.これが最も長い上昇サブシーケンスの問題であることは容易ではない.もう一つのケースは、各行または列が噴水を歩く場合は、噴水をまっすぐ行かなければならないということです.
コード#コード#

#include
#include
#include
#include
#include
#include
#define y1 yy1
#define y2 yy2
using namespace std;

const int N=200005;
const int inf=1e8;
const double pi=acos(-1);

int n,x1,x2,y2,y1,f[N],g[N],b[N];
struct data{int x,y;}a[N];

int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

bool cmp(data a,data b)
{
    return a.xint main()
{
    x1=read();y1=read();x2=read();y2=read();
    n=read();
    for (int i=1;i<=n;i++) a[i].x=read(),a[i].y=read();
    if (x1>x2)
    {
        x1=inf-x1;x2=inf-x2;
        for (int i=1;i<=n;i++) a[i].x=inf-a[i].x;
    }
    if (y1>y2)
    {
        y1=inf-y1;y2=inf-y2;
        for (int i=1;i<=n;i++) a[i].y=inf-a[i].y;
    }
    sort(a+1,a+n+1,cmp);
    int tot=0;
    for (int i=1;i<=n;i++)
        if (a[i].x>=x1&&a[i].x<=x2&&a[i].y>=y1&&a[i].y<=y2) b[++tot]=a[i].y;
    int mx=0;
    for (int i=1;i<=tot;i++)
    {
        f[i]=lower_bound(g+1,g+mx+1,b[i])-g;
        if (f[i]>mx) mx=f[i],g[mx]=b[i];
        else g[f[i]]=min(g[f[i]],b[i]);
    }
    double ans=(double)(x2+y2-x1-y1)*100;
    ans-=mx*(20-5*pi);
    if (mx==min(y2-y1+1,x2-x1+1)) ans+=5*pi;
    printf("%.12lf",ans);
    return 0;
}