Submission #1794718

---

Source Code Expand

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=200200,oo=1000000000;
const double pi=acos(-1.0);
int i,j,k,n,m,fgx,fgy,ch,ff,ans;
int lis[N];
double Ans;
struct cc {
	int x,y;
	bool operator < (const cc &n) const {
		return x<n.x;
	}
} S,T,t,A[N];
void R(int &x) {
	ff=x=0;ch=getchar();
	while (ch<'0' || '9'<ch) { if (ch=='-') ff=1;ch=getchar();}
	while ('0'<=ch && ch<='9') x=x*10+ch-'0',ch=getchar();
	if (ff) x=-x;
}
int main() {
	R(S.x);R(S.y);R(T.x);R(T.y);
	if (S.x>T.x) fgx=-1,S.x=-S.x,T.x=-T.x;
	else fgx=1;
	if (S.y>T.y) fgy=-1,S.y=-S.y,T.y=-T.y;
	else fgy=1;
	R(n);
	for (i=1;i<=n;i++) {
		R(t.x);R(t.y);
		t.x*=fgx;
		t.y*=fgy;
		if (S.x<=t.x && t.x<=T.x && S.y<=t.y && t.y<=T.y) A[++m]=t;
	}
	sort(A+1,A+m+1);
	ans=0;
	lis[0]=-oo;
	for (i=1;i<=m;i++) {
		if (A[i].y>lis[ans]) lis[++ans]=A[i].y;
		else {
			int l=0,r=ans,mid;
			while (l<r) {
				mid=(l+r+1)>>1;
				if (lis[mid]<A[i].y) l=mid;
				else r=mid-1;
			}
			lis[l+1]=A[i].y;
		}
	}
	Ans=(T.x+T.y-S.x-S.y)*100.0;
	Ans+=5.0*pi*ans-20.0*ans;
	if (T.x-S.x+1==ans || T.y-S.y+1==ans) Ans+=5.0*pi;
	printf("%.15lf\n",Ans);
}

Submission Info

Judge Result