Submission #1541283
Source Code Expand
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
typedef long long ll;
struct segtree{
static const int N=1<<18;
int seg[N*2];
segtree(){
rep(i,N*2) seg[i]=0;
}
void update(int x,int v){
x+=N;
seg[x]=v;
x/=2;
while(x){
seg[x]=max(seg[x*2],seg[x*2+1]);
x/=2;
}
}
int getmax(int a,int b,int l=0,int r=N,int k=1){
if(b<=l||r<=a) return 0;
if(a<=l&&r<=b) return seg[k];
return max(getmax(a,b,l,(l+r)/2,k*2),getmax(a,b,(l+r)/2,r,k*2+1));
}
}seg;
double pi = acos(-1);
const int MN = 200010;
ll sx,sy,tx,ty;
ll N;
ll x[MN],y[MN];
void input(){
bool swapped = 0;
cin>>sx>>sy>>tx>>ty;
if(sy==ty){
swapped = 1;
swap(sx,sy);
swap(tx,ty);
}
cin>>N;
rep(i,N){
cin>>x[i]>>y[i];
if(swapped) swap(x[i],y[i]);
}
}
int main(){
input();
if(sx==tx){
bool is = 0;
if(sy>ty) swap(sy,ty);
rep(i,N){
if(x[i] == sx && sy<y[i] && y[i]<ty) is = 1;
}
double ans = (ty-sy)*100;
if(is) ans += -20 + 10*pi;
printf("%.12f\n",ans);
return 0;
}
if(sx>tx){
swap(sx,tx);swap(sy,ty);
}
if(sy>ty){
int X = 1e8;
sy = X - sy;
ty = X - ty;
rep(i,N) y[i] = X - y[i];
}
using P = pair<int,int>;
vector<P> ps;
rep(i,N){
if(sx<=x[i]&&x[i]<=tx&&sy<=y[i]&&y[i]<=ty) ps.pb(P(x[i],y[i]));
}
sort(all(ps));
N = ps.size();
vector<int> xs,ys;
for(P p:ps){
ys.pb(p.sc);
}
sort(all(ys));
rep(i,N){
y[i] = lower_bound(all(ys),ps[i].sc) - ys.begin();
}
int is = 0;
rep(i,N){
int v = seg.getmax(0,y[i])+1;
seg.update(y[i],v);
chmax(is,v);
}
double ans = ((tx-sx) + (ty-sy))*100 - is*(20-5*pi);
printf("%.12f\n",ans);
}
Submission Info
Submission Time |
|
Task |
C - Fountain Walk |
User |
sigma425 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2244 Byte |
Status |
WA |
Exec Time |
242 ms |
Memory |
8816 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 |
3 ms |
3456 KB |
sample_02.txt |
AC |
3 ms |
3456 KB |
sample_03.txt |
AC |
3 ms |
3456 KB |
subtask_1_01.txt |
AC |
3 ms |
3456 KB |
subtask_1_02.txt |
AC |
3 ms |
3456 KB |
subtask_1_03.txt |
AC |
3 ms |
3456 KB |
subtask_1_04.txt |
AC |
3 ms |
3456 KB |
subtask_1_05.txt |
AC |
3 ms |
3456 KB |
subtask_1_06.txt |
AC |
3 ms |
3456 KB |
subtask_1_07.txt |
AC |
3 ms |
3456 KB |
subtask_1_08.txt |
AC |
3 ms |
3456 KB |
subtask_1_09.txt |
AC |
53 ms |
4352 KB |
subtask_1_10.txt |
WA |
109 ms |
4992 KB |
subtask_1_11.txt |
WA |
30 ms |
3968 KB |
subtask_1_12.txt |
WA |
202 ms |
8816 KB |
subtask_1_13.txt |
AC |
114 ms |
5120 KB |
subtask_1_14.txt |
WA |
54 ms |
4352 KB |
subtask_1_15.txt |
WA |
27 ms |
3968 KB |
subtask_1_16.txt |
WA |
202 ms |
8816 KB |
subtask_1_17.txt |
AC |
95 ms |
4864 KB |
subtask_1_18.txt |
AC |
75 ms |
4608 KB |
subtask_1_19.txt |
AC |
74 ms |
4736 KB |
subtask_1_20.txt |
AC |
191 ms |
8816 KB |
subtask_1_21.txt |
AC |
212 ms |
8816 KB |
subtask_1_22.txt |
AC |
204 ms |
8816 KB |
subtask_1_23.txt |
AC |
207 ms |
8816 KB |
subtask_1_24.txt |
AC |
3 ms |
3456 KB |
subtask_1_25.txt |
AC |
3 ms |
3456 KB |
subtask_1_26.txt |
AC |
3 ms |
3456 KB |
subtask_1_27.txt |
AC |
3 ms |
3456 KB |
subtask_1_28.txt |
AC |
121 ms |
5504 KB |
subtask_1_29.txt |
AC |
151 ms |
5504 KB |
subtask_1_30.txt |
AC |
242 ms |
8816 KB |
subtask_1_31.txt |
AC |
162 ms |
8816 KB |
subtask_1_32.txt |
AC |
162 ms |
8816 KB |
subtask_1_33.txt |
AC |
163 ms |
8816 KB |
subtask_1_34.txt |
AC |
167 ms |
8816 KB |
subtask_1_35.txt |
AC |
195 ms |
8816 KB |
subtask_1_36.txt |
AC |
231 ms |
8816 KB |
subtask_1_37.txt |
AC |
196 ms |
8816 KB |
subtask_1_38.txt |
AC |
190 ms |
8816 KB |
subtask_1_39.txt |
AC |
200 ms |
8816 KB |
subtask_1_40.txt |
AC |
193 ms |
8816 KB |
subtask_1_41.txt |
AC |
199 ms |
8816 KB |