rt,卡在 subtask_1_02 那一个也仅是那一个点,求调
#include <bits/stdc++.h>
#define int long long
#define Pi M_PI
using namespace std;
const int maxn=2e5+5;
int sx,sy,ex,ey;
struct node
{
int x,y;
friend bool operator<(node x,node y)
{
return x.x<y.x;
}
} p[maxn];
int n,tot,len,x[maxn];
signed main()
{
cin >>sx>>sy>>ex>>ey>>n;
if(sx>ex)
swap(sx,ex),swap(sy,ey);
for(int i=1;i<=n;i++)
{
cin >>p[i].x>>p[i].y;
if((p[i].x<=ex&&p[i].x>=sx&&p[i].y>=min(sy,ey)&&p[i].y<=max(sy,ey)))
p[++tot]=p[i];
}
n=tot;
sort(p+1,p+n+1);
if(sx==ex&&sy==ey)
{
cout <<0<<endl;
return 0;
}
if(sy<ey)
{
for(int i=1;i<=n;i++)
{
if(p[i].y>x[len])
x[++len]=p[i].y;
else
x[lower_bound(x+1,x+len+1,p[i].y)-x]=p[i].y;
}
// cout <<len<<endl;
if(len==min(ex-sx+1,ey-sy+1))
printf("%.20lf",100.0*(ex-sx+ey-sy)+((double)(len)-1)*(M_PI*5-20)+(M_PI*10-20));
else
printf("%.20lf",100.0*(ex-sx+ey-sy)+len*(Pi*5-20));
}
else
{
for(int i=n;i>=1;i--)
{
if(p[i].y>x[len])
x[++len]=p[i].y;
else
x[lower_bound(x+1,x+len+1,p[i].y)-x]=p[i].y;
}
if(len==min(ex-sx+1,sy-ey+1))
printf("%.20lf",100.0*(ex-sx+sy-ey)+((double)(len)-1)*(Pi*5-20)+(Pi*10-20));
else
printf("%.20lf",100.0*(ex-sx+sy-ey)+len*(Pi*5-20));
}
return 0;
}
/*
3 3 1 1
2
1 3
3 2
*/