Submission #2866777


Source Code Expand

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<n;i++)
#define loop(i,a,n) for(i=a;i<n;i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define int ll
typedef vector<int> vi;
typedef pair<int,int> pii;
int sx,sy,gx,gy;

bool range(int x,int y){
  if(min(sx,gx)<=x && x<=max(sx,gx) && 
     min(sy,gy)<=y && y<=max(sy,gy))
    return true;
  return false;
}

signed main(void) {
  int i,j;
  int x1,x2,y1,y2,n;
  cin>>x1>>y1>>x2>>y2;
  sx=min(x1,x2);
  gx=max(x1,x2);
  sy=min(y1,y2);
  gy=max(y1,y2);
  cin>>n;
  pii p[200000];
  rep(i,n){
    cin>>p[i].first>>p[i].second;
    if(!range(p[i].first,p[i].second))i--,n--;
  }
  if(x1>x2)rep(i,n)p[i].first*=-1;
  if(y1>y2)rep(i,n)p[i].second*=-1;
  int num=0;
  if(n){
    sort(p,p+n);
    vi v(n);
    rep(i,n)v[i]=p[i].second;
    int dp[100000]; 
    fill(dp,dp+n,INF);
    rep(i,n) *lower_bound(dp,dp+n,v[i])=v[i];
    num=lower_bound(dp,dp+n,INF)-dp;
  }
  ld ans=(ll)(abs(sx-gx)+abs(sy-gy))*100;
  if(abs(num-abs(sx-gx)-1)<EPS || abs(num-abs(sy-gy)-1)<EPS)
    ans+=5*3.141592653589793238;
  cout<<shosu(13)<<ans-20*num+num*5*3.141592653589793238<<endl;
}

Submission Info

Submission Time
Task C - Fountain Walk
User rika0384
Language C++14 (GCC 5.4.1)
Score 900
Code Size 1580 Byte
Status AC
Exec Time 172 ms
Memory 5760 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 900 / 900
Status
AC × 3
AC × 47
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 3968 KB
sample_02.txt AC 2 ms 3328 KB
sample_03.txt AC 2 ms 3328 KB
subtask_1_01.txt AC 2 ms 3328 KB
subtask_1_02.txt AC 2 ms 3584 KB
subtask_1_03.txt AC 2 ms 3456 KB
subtask_1_04.txt AC 2 ms 3328 KB
subtask_1_05.txt AC 2 ms 3328 KB
subtask_1_06.txt AC 2 ms 3328 KB
subtask_1_07.txt AC 2 ms 3328 KB
subtask_1_08.txt AC 2 ms 3328 KB
subtask_1_09.txt AC 52 ms 3328 KB
subtask_1_10.txt AC 107 ms 3328 KB
subtask_1_11.txt AC 29 ms 3328 KB
subtask_1_12.txt AC 172 ms 5760 KB
subtask_1_13.txt AC 114 ms 3328 KB
subtask_1_14.txt AC 53 ms 3584 KB
subtask_1_15.txt AC 27 ms 3328 KB
subtask_1_16.txt AC 171 ms 5760 KB
subtask_1_17.txt AC 95 ms 3328 KB
subtask_1_18.txt AC 74 ms 3456 KB
subtask_1_19.txt AC 72 ms 3456 KB
subtask_1_20.txt AC 160 ms 5760 KB
subtask_1_21.txt AC 171 ms 5760 KB
subtask_1_22.txt AC 171 ms 5760 KB
subtask_1_23.txt AC 171 ms 5760 KB
subtask_1_24.txt AC 2 ms 3712 KB
subtask_1_25.txt AC 2 ms 3328 KB
subtask_1_26.txt AC 2 ms 3712 KB
subtask_1_27.txt AC 2 ms 3840 KB
subtask_1_28.txt AC 118 ms 3584 KB
subtask_1_29.txt AC 146 ms 3968 KB
subtask_1_30.txt AC 171 ms 5760 KB
subtask_1_31.txt AC 125 ms 5760 KB
subtask_1_32.txt AC 132 ms 5760 KB
subtask_1_33.txt AC 131 ms 5760 KB
subtask_1_34.txt AC 127 ms 5760 KB
subtask_1_35.txt AC 159 ms 5760 KB
subtask_1_36.txt AC 160 ms 5760 KB
subtask_1_37.txt AC 160 ms 5760 KB
subtask_1_38.txt AC 159 ms 5760 KB
subtask_1_39.txt AC 160 ms 5760 KB
subtask_1_40.txt AC 156 ms 5760 KB
subtask_1_41.txt AC 156 ms 5760 KB