Submission #5893030
Source Code Expand
#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof x)
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define Fod(i,b,a) for (int i=(b);i>=(a);i--)
#define fi first
#define se second
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define outval(x) cerr<<#x" = "<<x<<endl
#define outtag(x) cerr<<"---------------"#x"---------------"<<endl
#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\
For(_x,L,R)cerr<<a[_x]<<" ";cerr<<endl;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector <int> vi;
LL read(){
LL x=0,f=0;
char ch=getchar();
while (!isdigit(ch))
f|=ch=='-',ch=getchar();
while (isdigit(ch))
x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return f?-x:x;
}
const int N=2e5+5;
int n;
struct Point{
int x,y;
void get(){
x=read(),y=read();
}
}p[N],p1,p2;
bool cmp(Point a,Point b){
if (a.y!=b.y)
return a.y<b.y;
return a.x<b.x;
}
int lim=1e8;
int Ha[N],hs;
void LSH(){
int c=0;
For(i,1,n)
if (p1.x<=p[i].x&&p[i].x<=p2.x&&p1.y<=p[i].y&&p[i].y<=p2.y)
p[++c]=p[i];
n=c,hs=0;
For(i,1,n)
Ha[++hs]=p[i].x;
Ha[++hs]=p1.x,Ha[++hs]=p2.x;
sort(Ha+1,Ha+hs+1);
hs=unique(Ha+1,Ha+hs+1)-Ha-1;
For(i,1,n)
p[i].x=lower_bound(Ha+1,Ha+hs+1,p[i].x)-Ha;
p1.x=lower_bound(Ha+1,Ha+hs+1,p1.x)-Ha;
p2.x=lower_bound(Ha+1,Ha+hs+1,p2.x)-Ha;
}
namespace bit{
int c[N];
void init(){
clr(c);
}
void Add(int x,int d){
for (;x<=n+2;x+=x&-x)
c[x]=max(c[x],d);
}
int Ask(int x){
int ans=0;
for (;x;x-=x&-x)
ans=max(ans,c[x]);
return ans;
}
}
double PI=acos(-1.0);
int main(){
p1.get(),p2.get();
n=read();
For(i,1,n)
p[i].get();
if (p1.x>p2.x)
swap(p1,p2);
if (p1.y>p2.y){
p1.y=lim-p1.y-1;
p2.y=lim-p2.y-1;
For(i,1,n)
p[i].y=lim-p[i].y-1;
}
LSH();
bit::init();
sort(p+1,p+n+1,cmp);
For(i,1,n){
int v=bit::Ask(p[i].x)+1;
bit::Add(p[i].x,v);
}
int len=bit::Ask(p2.x);
double ans=100.0*(Ha[p2.x]+p2.y-Ha[p1.x]-p1.y);
ans+=(PI/2-2)*10*len;
if (len==min(Ha[p2.x]-Ha[p1.x],p2.y-p1.y)+1)
ans+=PI/2*10*len;
printf("%.13lf\n",ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Fountain Walk |
User |
zhouzhendong |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2155 Byte |
Status |
WA |
Exec Time |
100 ms |
Memory |
3328 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 900 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_40.txt, subtask_1_41.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
2 ms |
1024 KB |
sample_02.txt |
AC |
2 ms |
1024 KB |
sample_03.txt |
AC |
2 ms |
1024 KB |
subtask_1_01.txt |
AC |
2 ms |
1024 KB |
subtask_1_02.txt |
AC |
2 ms |
1024 KB |
subtask_1_03.txt |
AC |
2 ms |
1024 KB |
subtask_1_04.txt |
AC |
2 ms |
1024 KB |
subtask_1_05.txt |
AC |
2 ms |
1024 KB |
subtask_1_06.txt |
AC |
2 ms |
1024 KB |
subtask_1_07.txt |
AC |
2 ms |
1024 KB |
subtask_1_08.txt |
AC |
2 ms |
1024 KB |
subtask_1_09.txt |
AC |
12 ms |
1536 KB |
subtask_1_10.txt |
WA |
23 ms |
2176 KB |
subtask_1_11.txt |
WA |
7 ms |
1280 KB |
subtask_1_12.txt |
WA |
96 ms |
3328 KB |
subtask_1_13.txt |
AC |
25 ms |
2304 KB |
subtask_1_14.txt |
WA |
12 ms |
1536 KB |
subtask_1_15.txt |
WA |
6 ms |
1280 KB |
subtask_1_16.txt |
WA |
96 ms |
3328 KB |
subtask_1_17.txt |
AC |
20 ms |
2048 KB |
subtask_1_18.txt |
AC |
16 ms |
1792 KB |
subtask_1_19.txt |
AC |
16 ms |
1792 KB |
subtask_1_20.txt |
AC |
93 ms |
3328 KB |
subtask_1_21.txt |
AC |
96 ms |
3328 KB |
subtask_1_22.txt |
AC |
96 ms |
3328 KB |
subtask_1_23.txt |
AC |
96 ms |
3328 KB |
subtask_1_24.txt |
AC |
2 ms |
1024 KB |
subtask_1_25.txt |
AC |
2 ms |
1024 KB |
subtask_1_26.txt |
AC |
2 ms |
1024 KB |
subtask_1_27.txt |
AC |
2 ms |
1024 KB |
subtask_1_28.txt |
AC |
27 ms |
2560 KB |
subtask_1_29.txt |
AC |
32 ms |
2560 KB |
subtask_1_30.txt |
AC |
100 ms |
3328 KB |
subtask_1_31.txt |
AC |
53 ms |
3328 KB |
subtask_1_32.txt |
AC |
57 ms |
3328 KB |
subtask_1_33.txt |
AC |
55 ms |
3328 KB |
subtask_1_34.txt |
AC |
62 ms |
3328 KB |
subtask_1_35.txt |
AC |
71 ms |
3328 KB |
subtask_1_36.txt |
AC |
75 ms |
3328 KB |
subtask_1_37.txt |
AC |
73 ms |
3328 KB |
subtask_1_38.txt |
AC |
60 ms |
3328 KB |
subtask_1_39.txt |
AC |
80 ms |
3328 KB |
subtask_1_40.txt |
AC |
61 ms |
3328 KB |
subtask_1_41.txt |
AC |
61 ms |
3328 KB |