Submission #2294034
Source Code Expand
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define MN 200005
using namespace std;
int n,sx,sy,tx,ty,maxn=1e8,top,st[MN],ans,y[MN],lst,resnow[MN];
struct po{int x,y;}p[MN];
bool cmp(po x,po y){return x.x==y.x?x.y<y.y:x.x<y.x;}
int main(){
scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&p[i].x,&p[i].y);
if(tx<sx)swap(sx,tx),swap(sy,ty);
if(sy>ty){
sy=maxn-sy,ty=maxn-ty;for(int i=1;i<=n;i++)p[i].y=maxn-p[i].y;
}int resx=sx,resy=sy,retx=tx,rety=ty;p[++n]=(po){sx,sy},p[++n]=(po){tx,ty};
for(int i=1;i<=n;i++)y[i]=p[i].y;sort(p+1,p+n+1,cmp);sort(y+1,y+n+1);int ny=unique(y+1,y+n+1)-y;
for(int i=1;i<=n;i++)p[i].y=lower_bound(y+1,y+ny,p[i].y)-y;
sy=lower_bound(y+1,y+ny,sy)-y,ty=lower_bound(y+1,y+ny,ty)-y;int i;st[0]=0;
for(int i=1;i<=n;i++)st[i]=n+1;
for(i=1;i<=n;i++)if(p[i].y>=sy&&p[i].y<=ty&&p[i].x>=sx&&p[i].x<=tx){
if(p[i].x==sx&&p[i].y==sy)continue;
resnow[i]=upper_bound(st,st+n+1,p[i].y)-st;
st[resnow[i]]=p[i].y;
if(p[i].x==tx&&p[i].y==ty)break;
}ans=resnow[i]-1;
double res=1.0*(retx-resx+rety-resy)*100;res+=1.0*(acos(-1)-4)*5*ans;
if(ans==min(retx-resx+1,rety-resy+1))res+=5.0*(ans!=0)*acos(-1);printf("%.15f\n",res);
}
Submission Info
Submission Time |
|
Task |
C - Fountain Walk |
User |
luogu_bot2 |
Language |
C++ (GCC 5.4.1) |
Score |
900 |
Code Size |
1221 Byte |
Status |
AC |
Exec Time |
107 ms |
Memory |
4096 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:11:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
^
./Main.cpp:12:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:13:52: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=n;i++)scanf("%d%d",&p[i].x,&p[i].y);
^
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 |
1 ms |
128 KB |
sample_02.txt |
AC |
1 ms |
128 KB |
sample_03.txt |
AC |
1 ms |
128 KB |
subtask_1_01.txt |
AC |
1 ms |
128 KB |
subtask_1_02.txt |
AC |
1 ms |
128 KB |
subtask_1_03.txt |
AC |
1 ms |
128 KB |
subtask_1_04.txt |
AC |
1 ms |
128 KB |
subtask_1_05.txt |
AC |
1 ms |
128 KB |
subtask_1_06.txt |
AC |
1 ms |
128 KB |
subtask_1_07.txt |
AC |
1 ms |
128 KB |
subtask_1_08.txt |
AC |
1 ms |
128 KB |
subtask_1_09.txt |
AC |
31 ms |
1280 KB |
subtask_1_10.txt |
AC |
69 ms |
2432 KB |
subtask_1_11.txt |
AC |
16 ms |
768 KB |
subtask_1_12.txt |
AC |
93 ms |
4096 KB |
subtask_1_13.txt |
AC |
74 ms |
2560 KB |
subtask_1_14.txt |
AC |
32 ms |
1280 KB |
subtask_1_15.txt |
AC |
15 ms |
768 KB |
subtask_1_16.txt |
AC |
93 ms |
4096 KB |
subtask_1_17.txt |
AC |
61 ms |
2176 KB |
subtask_1_18.txt |
AC |
47 ms |
1920 KB |
subtask_1_19.txt |
AC |
45 ms |
2048 KB |
subtask_1_20.txt |
AC |
91 ms |
4096 KB |
subtask_1_21.txt |
AC |
93 ms |
4096 KB |
subtask_1_22.txt |
AC |
94 ms |
4096 KB |
subtask_1_23.txt |
AC |
93 ms |
4096 KB |
subtask_1_24.txt |
AC |
1 ms |
128 KB |
subtask_1_25.txt |
AC |
1 ms |
128 KB |
subtask_1_26.txt |
AC |
1 ms |
128 KB |
subtask_1_27.txt |
AC |
1 ms |
128 KB |
subtask_1_28.txt |
AC |
94 ms |
3712 KB |
subtask_1_29.txt |
AC |
97 ms |
3456 KB |
subtask_1_30.txt |
AC |
107 ms |
4096 KB |
subtask_1_31.txt |
AC |
76 ms |
4096 KB |
subtask_1_32.txt |
AC |
69 ms |
4096 KB |
subtask_1_33.txt |
AC |
68 ms |
4096 KB |
subtask_1_34.txt |
AC |
66 ms |
4096 KB |
subtask_1_35.txt |
AC |
77 ms |
4096 KB |
subtask_1_36.txt |
AC |
98 ms |
4096 KB |
subtask_1_37.txt |
AC |
86 ms |
4096 KB |
subtask_1_38.txt |
AC |
80 ms |
4096 KB |
subtask_1_39.txt |
AC |
83 ms |
4096 KB |
subtask_1_40.txt |
AC |
84 ms |
4096 KB |
subtask_1_41.txt |
AC |
70 ms |
4096 KB |