AGC 019 C-欲張り-線分樹

网の辺の长さの100、一部の格の点は半径の10の円盘があります.エッジとディスクの境界に沿ってしか歩けず、ディスクに入ることはできません.ある点から別の点への最短ルートを聞く.メッシュ図サイズ1 e 8、ディスク個数1 e 5.同じ横線または縦線に2つの円盤は存在しません.标题:円盤は遠回りしかできないように見えますが、実はそうではありません.(x,y)から(x+1,y+1)まで歩き、(x+1,y)に円盤が1つあれば、その円盤で2 R-0.5 PI*Rの道のりを節約できます.そして境界の場合(始点から終点までの内部に皿がないなど)を除いて、できるだけ多くの場合、この線分の木を一度にするとよい.境界の場合|x 1-x 2+1|または|y 1-y 2+1|に等しい場合、最後に半円を通過する場合、これは特判である.

    #include
    #define gc getchar()
    #define rep(i,a,b) for(int i=a;i<=b;i++)
    #define Rep(i,v) rep(i,0,(int)v.size()-1)
    #define lint long long
    #define db double
    #define pb push_back
    #define mp make_pair
    #define fir first
    #define sec second
    #define debug(x) cerr<
    #define sp <
    #define ln <
    using namespace std;typedef pair<int,int> pii;const int N=200010;const db PI=acos(-1.0),R=10.0,L=100.0;
    inline int inn() { int x,ch;while((ch=gc)<'0'||ch>'9');x=ch^'0';while((ch=gc)>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^'0');return x; }
    struct segment { int l,r,v;segment *ch[2]; }*rt;pii p[N];vector<int> v;
    int build(segment* &rt,int l,int r)
    {
    	rt=new segment,rt->l=l,rt->r=r,rt->v=0;
    	if(l==r) return 0;int mid=(l+r)>>1;
    	return build(rt->ch[0],l,mid),build(rt->ch[1],mid+1,r);
    }
    int update(segment* &rt,int p,int v)
    {
    	int l=rt->l,r=rt->r,mid=(l+r)>>1;
    	if(l==r) return rt->v=v;
    	if(p<=mid) update(rt->ch[0],p,v);
    	else update(rt->ch[1],p,v);
    	return rt->v=max(rt->ch[0]->v,rt->ch[1]->v);
    }
    int query(segment* &rt,int s,int t)
    {
    	int l=rt->l,r=rt->r,mid=(l+r)>>1;
    	if(s<=l&&r<=t) return rt->v;int ans=0;
    	if(s<=mid) ans=max(ans,query(rt->ch[0],s,t));
    	if(mid<t) ans=max(ans,query(rt->ch[1],s,t));
    	return ans;
    }
    #define rev(y) (y=-y)
    int main()
    {
    	int x1=inn(),y1=inn(),x2=inn(),y2=inn(),n=inn(),revt=0,cnt=0,ans=0,x,y,t;
    	if(x1>x2) swap(x1,x2),swap(y1,y2);if(y1>y2) revt=1,rev(y1),rev(y2);
    	rep(i,1,n) { x=inn(),y=inn();if(revt) rev(y);if(x<x1||x>x2||y<y1||y>y2) continue;p[++cnt]=mp(x,y); }
    	if(x1==x2||y1==y2) return !printf("%.12lf
",double(L*(x2-x1+y2-y1)+(PI-2)*R*cnt));
    	if(!cnt) return !printf("%.12lf
",double(L*(x2-x1+y2-y1)));
    	n=cnt,sort(p+1,p+n+1),build(rt,1,n);rep(i,1,n) v.pb(p[i].sec);sort(v.begin(),v.end());
    	rep(i,1,n) p[i].sec=lower_bound(v.begin(),v.end(),p[i].sec)-v.begin()+1;
    	rep(i,1,n) t=query(rt,1,p[i].sec)+1,ans=max(ans,t),update(rt,p[i].sec,t);
    	db Ans=L*(x2-x1+y2-y1)-ans*(2-0.5*PI)*R;
    	if(x2-x1+1==ans||y2-y1+1==ans) Ans+=0.5*PI*R;
    	return !printf("%.12lf",double(Ans));
    }