Submission #1540587

---

Source Code Expand

#include <cstdio>
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <map>

#define MAX_INT 2147483647
#define PI 3.14159265358979323846
#define long long long int

static const int MAX = 100000000;
using std::vector;
using std::map;
using std::string;
using std::pair;
using std::cin;
using std::cout;
using std::cerr;

// @author: pashka

int main() {
    std::ios::sync_with_stdio(false);

    int x1, y1, x2, y2, n;

    cin >> x1 >> y1 >> x2 >> y2 >> n;

    vector<pair<int, int>> c(n);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        c[i] = {x, y};
    }

    if (x1 > x2) {
        x1 = MAX - x1;
        x2 = MAX - x2;
        for (auto &item : c) {
            item.first = MAX - item.first;
        }
    }
    if (y1 > y2) {
        y1 = MAX - y1;
        y2 = MAX - y2;
        for (auto &item : c) {
            item.second = MAX - item.second;
        }
    }

    vector<pair<int, int>> good;
    for (auto item : c) {
        if (item.first >= x1 && item.first <= x2 && item.second >= y1 && item.second <= y2) {
            good.push_back(item);
        }
    }

    sort(good.begin(), good.end());
    int max = 0;
    vector<int> p(good.size() + 1, MAX_INT);

    for (auto item : good) {
        int l = -1;
        int r = p.size() + 1;
        while (r > l + 1) {
            int m = (l + r) / 2;
            if (p[m] > item.second) {
                r = m;
            } else {
                l = m;
            }
        }
        p[r] = item.second;
        max = std::max(max, r + 1);
    }

//    cerr << max << "\n";

    double res = 100 * (x2 - x1 + y2 - y1);
    if (x1 == x2 || y1 == y2) {
        res += 10 * max * (PI - 2);
    } else {
        res += 10 * max * (PI / 2 - 2);
    }

    cout << std::setprecision(20);
    cout << res << "\n";

    return 0;
}

Submission Info

Judge Result