Submission #1542283

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
typedef long long ll;

struct segtree{
	static const int N=1<<18;
	int seg[N*2];
	segtree(){
		rep(i,N*2) seg[i]=0;
	}
	void update(int x,int v){
		x+=N;
		seg[x]=v;
		x/=2;
		while(x){
			seg[x]=max(seg[x*2],seg[x*2+1]);
			x/=2;
		}
	}
	int getmax(int a,int b,int l=0,int r=N,int k=1){
		if(b<=l||r<=a) return 0;
		if(a<=l&&r<=b) return seg[k];
		return max(getmax(a,b,l,(l+r)/2,k*2),getmax(a,b,(l+r)/2,r,k*2+1));
	}
}seg;


double pi = acos(-1);
const int MN = 200010;
ll sx,sy,tx,ty;
ll N;
ll x[MN],y[MN];

void input(){
	bool swapped = 0;
	cin>>sx>>sy>>tx>>ty;
	if(sy==ty){
		swapped = 1;
		swap(sx,sy);
		swap(tx,ty);
	}
	cin>>N;
	rep(i,N){
		cin>>x[i]>>y[i];
		if(swapped) swap(x[i],y[i]);
	}
}
int main(){
	input();

	if(sx==tx){
		bool is = 0;
		if(sy>ty) swap(sy,ty);
		rep(i,N){
			if(x[i] == sx && sy<y[i] && y[i]<ty) is = 1;
		}
		double ans = (ty-sy)*100;
		if(is)  ans += -20 + 10*pi;
		printf("%.12f\n",ans);
		return 0;
	}

	if(sx>tx){
		swap(sx,tx);swap(sy,ty);
	}
	if(sy>ty){
		int X = 1e8;
		sy = X - sy;
		ty = X - ty;
		rep(i,N) y[i] = X - y[i];
	}

	using P = pair<int,int>;
	vector<P> ps;
	rep(i,N){
		if(sx<=x[i]&&x[i]<=tx&&sy<=y[i]&&y[i]<=ty) ps.pb(P(x[i],y[i]));
	}
	sort(all(ps));
	N = ps.size();
	vector<int> xs,ys;
	for(P p:ps){
		ys.pb(p.sc);
	}
	sort(all(ys));
	rep(i,N){
		y[i] = lower_bound(all(ys),ps[i].sc) - ys.begin();
	}
	int is = 0;
	rep(i,N){
		int v = seg.getmax(0,y[i])+1;
		seg.update(y[i],v);
		chmax(is,v);
	}
	double ans = ((tx-sx) + (ty-sy))*100 - is*(20-5*pi);
	if(is == min(tx-sx,ty-sy)+1){
		ans = ((tx-sx) + (ty-sy))*100 - (is-1)*(20-5*pi) + (-20 + 10*pi);
	}
	printf("%.12f\n",ans);
}

Submission Info

Judge Result