Submission #1911029

---

Source Code Expand

#include<set>
#include<cstdio> 
#include<cstring> 
#include<cmath> 
#include<algorithm> 
#include<ctime> 
#include<bits/stdc++.h>
using namespace std; 
#define pi  acos(-1)
#define ll int
#define For(i,x,y)  for(ll i=x;i<=y;++i) 
#define FOr(i,x,y)  for(ll i=x;i>=y;--i) 
#define rep(i,x,y)	for(ll i=x;i<y;++i)
ll read(){  ll x=0,f=1; char ch=getchar();  for(;ch<'0'||ch>'9';ch=getchar()) if (ch=='-')    f=-1;   for(;ch>='0'&&ch<='9';ch=getchar())   x=x*10+ch-'0';  return x*f; } 
void write(ll x){   if (x<0) putchar('-'),x=-x;  if (x>=10)   write(x/10);    putchar(x%10+'0');  } 
void writeln(ll x){ write(x);   puts("");   }
const ll N=500010;
struct data{	ll x,y;	}p[N];
ll c[N],x1,ya,x2,y2,ans,n,b[N];
void add(ll x,ll v){	for(;x<=n;x+=x&-x)	c[x]=max(c[x],v);	}
ll ask(ll x){	ll ans=-1e9;	for(;x;x-=x&-x)	ans=max(ans,c[x]);	return ans;	}
bool cmp(data a,data b){	return a.x==b.x?a.y<b.y:a.x<b.x;	}
int main(){
	memset(c,-60,sizeof c);
	x1=read();	ya=read();	x2=read();	y2=read();
	n=read();	For(i,1,n)	p[i].x=read(),p[i].y=read();
	if (x1>x2){	x1=-x1;	x2=-x2;	For(i,1,n)	p[i].x=-p[i].x;	}
	if (ya>y2){	ya=-ya;	y2=-y2;	For(i,1,n)	p[i].y=-p[i].y;	}
	p[++n]=(data){x1,ya};	p[++n]=(data){x2,y2};
	For(i,1,n)	b[i]=p[i].y;	sort(b+1,b+n+1);
	ll Y1=lower_bound(b+1,b+n+1,ya)-b,Y2=lower_bound(b+1,b+n+1,y2)-b;
	For(i,1,n)	p[i].y=lower_bound(b+1,b+n+1,p[i].y)-b;
	ll ans=0;
	sort(p+1,p+n+1,cmp);
	For(i,1,n){
		ll lis=ask(p[i].y)+1;
		if (p[i].x==x1&&p[i].y==Y1)	lis=0;
		else if (p[i].x==x2&&p[i].y==Y2)	ans=lis-1;
		add(p[i].y,lis);
	}
	printf("%.20lf",(x2-x1+y2-ya)*100.0+(pi-4)*5*ans+(ans==min(y2-ya+1,x2-x1+1)&&ans)*pi*5);
}

Submission Info

Judge Result