Contest Duration: ~ (local time) (150 minutes) Back to Home

Submission #1546371

Source Code Expand

Copy
```#include<bits/stdc++.h>

using namespace std;

const int INF = 1 << 30;

int main()
{
double cost = 20 * acos(-1) / 4.0;

int a, b, c, d, n, x[200000], y[200000];

cin >> a >> b >> c >> d;
cin >> n;
for(int i = 0; i < n; i++) {
cin >> x[i] >> y[i];
}

if(a > c) swap(a, c), swap(b, d);
bool flip = false;
if(b > d) swap(b, d), flip = true;

vector< pair< int, int > > idx;
for(int i = 0; i < n; i++) {
if(a <= x[i] && x[i] <= c && b <= y[i] && y[i] <= d) {
if(flip) idx.emplace_back(x[i], y[i] * -1);
else idx.emplace_back(x[i], y[i]);
}
}
sort(begin(idx), end(idx));

vector< int > dp(idx.size(), INF);
for(auto &p : idx) {
*lower_bound(begin(dp), end(dp), p.second) = p.second;
}
int pos = lower_bound(begin(dp), end(dp), INF) - begin(dp);
double ret = (c - a) * 100.0 + (d - b) * 100.0;
if(min(c - a, d - b) + 1 == pos) ret += cost;
ret -= pos * (20.0 - cost);
cout << fixed << setprecision(15) << ret << endl;
}```

Submission Info

Submission Time 2017-08-27 00:34:20+0900 C - Fountain Walk ei13333 C++14 (GCC 5.4.1) 900 1027 Byte AC 183 ms 4980 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
sample_01.txt 1 ms 256 KB
sample_02.txt 1 ms 256 KB
sample_03.txt 1 ms 256 KB