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

Submission #1545237

Source Code Expand

Copy
```#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <utility>
#include <functional>

#define REP(i,a,b) for(int i=int(a);i<int(b);i++)

using namespace std;

typedef long long int lli;
typedef pair<int,int> pii;

const double PI = acos(-1);
const int inf = 1 << 30;

int lis(vector<int> &v, int infi) {
vector<int> ans(v.size(), infi);
REP (i, 0, v.size()) {
(*lower_bound(ans.begin(), ans.end(), v[i])) = v[i];
}
return lower_bound(ans.begin(), ans.end(), infi) - ans.begin();
}

int sign(lli s) {
return (s >= 0 ? 1 : -1);
}

int main () {
lli sx, sy, gx, gy;
int N;
cin >> sx >> sy >> gx >> gy;
cin >> N;
vector<pii> XY(N);
int ml = sign((sx - gx) * (sy - gy));
REP (i, 0, N) cin >> XY[i].first >> XY[i].second;
double ans = 100 * (abs(sx - gx) + abs(sy - gy));
vector<pii> lim;
REP (i, 0, N) {
if (min(sx, gx) <= XY[i].first && XY[i].first <= max(sx, gx) && min(sy, gy) <= XY[i].second && XY[i].second <= max(sy, gy)) {
lim.push_back(XY[i]);
}
}
int mx = 0, my = 0;
{
sort(lim.begin(), lim.end(), [&](pii a, pii b) { return a.first < b.first;});
vector<int> temp;
REP (i, 0, lim.size()) {
temp.push_back(lim[i].second);
}
my = lis(temp, ml * inf);
}
{
sort(lim.begin(), lim.end(), [&](pii a, pii b) { return a.second < b.second;});
vector<int> temp;
REP (i, 0, lim.size()) {
temp.push_back(lim[i].first);
}
mx = lis(temp, ml * inf);
}
if (mx - 1 == abs(sx - gx) || my - 1 == abs(sy - gy)) {
ans += (10 * PI - 20) - (20 - 5 * PI) * (max(mx, my) - 1);
} else {
ans -= (20 - 5 * PI) * max(mx, my);
}
cout << fixed << setprecision(15) << ans << endl;
return 0;
}
```

#### Submission Info

Submission Time 2017-08-26 23:24:38+0900 C - Fountain Walk commy C++14 (GCC 5.4.1) 0 1965 Byte WA 201 ms 5232 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