Submission #2291586
Source Code Expand
#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=(b);++i)
#define F2(i,a,b) for(int i=a;i<(b);++i)
#define dF(i,a,b) for(int i=a;i>=(b);--i)
#define dF2(i,a,b) for(int i=a;i>(b);--i)
#define eF(i,u) for(int i=h[u];i;i=nxt[i])
#define ll long long
#define ld double
using namespace std;
ll Sx,Sy,Tx,Ty;
ll ansi,ansp=0;
int n,cnt,P[200001],Ans;
ll x[200001],y[200001];
ll X[200001],Y[200001],tmp[200001];
ll t[200001];
inline bool cmp(int p1,int p2){return X[p1]<X[p2];}
inline int BS(ll k){
int l=0,r=cnt,mid,ans;
while(l<=r){
mid=l+r>>1;
if(tmp[mid]>k) ans=mid, l=mid+1;
else r=mid-1;
}
return ans;
}
int main(){
scanf("%lld%lld%lld%lld",&Sx,&Sy,&Tx,&Ty);
ansi=abs(Sx-Tx)+abs(Sy-Ty); ansi*=10;
scanf("%d",&n);
F(i,1,n) scanf("%lld%lld",x+i,y+i);
if(Sx==Tx){
if(Sy>Ty) swap(Sy,Ty);
F(i,1,n) if(x[i]==Sx&&Sy<y[i]&&y[i]<Ty) ansi-=2, ansp+=10;
printf("%.15lf",10.*ansi+acos(-1)*ansp); return 0;
}
if(Sy==Ty){
if(Sx>Tx) swap(Sx,Tx);
F(i,1,n) if(y[i]==Sy&&Sx<x[i]&&x[i]<Tx) ansi-=2, ansp+=10;
printf("%.15lf",10.*ansi+acos(-1)*ansp); return 0;
}
if(Sx>Tx) swap(Sx,Tx), swap(Sy,Ty);
if(Sy<Ty)
F(i,1,n) if(Sx<=x[i]&&x[i]<=Tx&&Sy<=y[i]&&y[i]<=Ty) X[++cnt]=x[i], Y[cnt]=y[i], P[cnt]=cnt;
if(Sy>Ty)
F(i,1,n) if(Sx<=x[i]&&x[i]<=Tx&&Ty<=y[i]&&y[i]<=Sy) X[++cnt]=x[i], Y[cnt]=y[i], P[cnt]=cnt;
F(i,1,cnt) t[i]=Y[i];
sort(t+1,t+cnt+1);
F(i,1,cnt) Y[i]=lower_bound(t+1,t+cnt+1,Y[i])-t;
sort(P+1,P+cnt+1,cmp);
if(Sy<Ty){
memset(tmp,0x3f,sizeof tmp);
tmp[0]=0;
F(i,1,cnt){
int k=lower_bound(tmp,tmp+cnt+1,Y[P[i]])-tmp;
tmp[k]=min(tmp[k],Y[P[i]]);
Ans=max(Ans,k);
}
if(Ans==min(abs(Sx-Tx),abs(Sy-Ty))+1) printf("%.15lf",10.*(ansi-2*Ans)+acos(-1)*5*Ans+5*acos(-1));
else printf("%.15lf",10.*(ansi-2*Ans)+acos(-1)*5*Ans);
}
else{
tmp[0]=0x3f3f3f3f;
F(i,1,cnt){
int k=BS(Y[P[i]]);
tmp[k+1]=max(tmp[k+1],Y[P[i]]);
Ans=max(Ans,k+1);
}
if(Ans==min(abs(Sx-Tx),abs(Sy-Ty))+1) printf("%.15lf",10.*(ansi-2*Ans)+acos(-1)*5*Ans+5*acos(-1));
else printf("%.15lf",10.*(ansi-2*Ans)+acos(-1)*5*Ans);
}
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Fountain Walk |
User |
luogu_bot5 |
Language |
C++14 (GCC 5.4.1) |
Score |
900 |
Code Size |
2148 Byte |
Status |
AC |
Exec Time |
118 ms |
Memory |
10368 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:30:43: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld%lld",&Sx,&Sy,&Tx,&Ty);
^
./Main.cpp:32:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:33:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
F(i,1,n) scanf("%lld%lld",x+i,y+i);
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
900 / 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 |
3 ms |
6912 KB |
sample_02.txt |
AC |
2 ms |
2304 KB |
sample_03.txt |
AC |
2 ms |
2304 KB |
subtask_1_01.txt |
AC |
3 ms |
6912 KB |
subtask_1_02.txt |
AC |
2 ms |
6400 KB |
subtask_1_03.txt |
AC |
2 ms |
6400 KB |
subtask_1_04.txt |
AC |
3 ms |
6912 KB |
subtask_1_05.txt |
AC |
2 ms |
2304 KB |
subtask_1_06.txt |
AC |
2 ms |
2304 KB |
subtask_1_07.txt |
AC |
2 ms |
2304 KB |
subtask_1_08.txt |
AC |
2 ms |
2304 KB |
subtask_1_09.txt |
AC |
15 ms |
2432 KB |
subtask_1_10.txt |
AC |
31 ms |
7680 KB |
subtask_1_11.txt |
AC |
10 ms |
6912 KB |
subtask_1_12.txt |
AC |
118 ms |
10368 KB |
subtask_1_13.txt |
AC |
32 ms |
3200 KB |
subtask_1_14.txt |
AC |
16 ms |
6528 KB |
subtask_1_15.txt |
AC |
9 ms |
6912 KB |
subtask_1_16.txt |
AC |
116 ms |
10368 KB |
subtask_1_17.txt |
AC |
27 ms |
7552 KB |
subtask_1_18.txt |
AC |
22 ms |
6784 KB |
subtask_1_19.txt |
AC |
22 ms |
7296 KB |
subtask_1_20.txt |
AC |
112 ms |
10368 KB |
subtask_1_21.txt |
AC |
116 ms |
10368 KB |
subtask_1_22.txt |
AC |
117 ms |
10368 KB |
subtask_1_23.txt |
AC |
118 ms |
10368 KB |
subtask_1_24.txt |
AC |
2 ms |
2304 KB |
subtask_1_25.txt |
AC |
2 ms |
2304 KB |
subtask_1_26.txt |
AC |
2 ms |
2304 KB |
subtask_1_27.txt |
AC |
2 ms |
2304 KB |
subtask_1_28.txt |
AC |
40 ms |
8192 KB |
subtask_1_29.txt |
AC |
43 ms |
7680 KB |
subtask_1_30.txt |
AC |
118 ms |
10368 KB |
subtask_1_31.txt |
AC |
62 ms |
10368 KB |
subtask_1_32.txt |
AC |
69 ms |
10368 KB |
subtask_1_33.txt |
AC |
68 ms |
10368 KB |
subtask_1_34.txt |
AC |
66 ms |
10368 KB |
subtask_1_35.txt |
AC |
78 ms |
10368 KB |
subtask_1_36.txt |
AC |
102 ms |
10368 KB |
subtask_1_37.txt |
AC |
80 ms |
10368 KB |
subtask_1_38.txt |
AC |
73 ms |
10368 KB |
subtask_1_39.txt |
AC |
83 ms |
10368 KB |
subtask_1_40.txt |
AC |
71 ms |
10368 KB |
subtask_1_41.txt |
AC |
70 ms |
10368 KB |