Submission #5306998

---

Source Code Expand

#include <stdio.h>
#include <assert.h>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <array>
#include <vector>
#include <queue>
#include <set>
#include <cmath>
#include <iomanip>
//#include <unordered_map>
//#include <unordered_set>
//#include <boost/container/static_vector.hpp>
//#include <boost/unordered_set.hpp>
//#include <boost/unordered_map.hpp>
//#include <unistd.h>

//#include <cv.h>
//#include <highgui.h>
#include <stdlib.h>
#include <string>

const int MAX_N = 200050;
const int MAX_L = 100000000;
int x1, y1, x2, y2;
int N;
int X[MAX_N], Y[MAX_N];

int seq[MAX_N], dp_lis[MAX_N];

int main(int argc, char **argv) {
    std::cin >> x1 >> y1 >> x2 >> y2;
    std::cin >> N;

    for (int i = 1; i <= N; i++) {
        std::cin >> X[i] >> Y[i];
    }

    if (x2 < x1) {
        for (int i = 1; i <= N; i++) {
            X[i] = MAX_L - 1 - X[i];
        }
        x1 = MAX_L - 1 - x1;
        x2 = MAX_L - 1 - x2;
    }

    if (y2 < y1) {
        for (int i = 1; i <= N; i++) {
            Y[i] = MAX_L - 1 - Y[i];
        }
        y1 = MAX_L - 1 - y1;
        y2 = MAX_L - 1 - y2;
    }

    std::vector<std::pair<int, int>> vec;

    for (int i = 1; i <= N; i++) {
        if (x1 <= X[i] && X[i] <= x2 && y1 <= Y[i] && Y[i] <= y2) {
            vec.push_back(std::pair<int, int>({X[i], Y[i]}));
        }
    }

    std::sort(vec.begin(), vec.end(),
        [](const std::pair<int, int>& a, const std::pair<int, int> b) { return a.first < b.first; }
    );

    int seq_size = vec.size();

    for (int i = 1; i <= seq_size; i++) {
        seq[i] = vec[i-1].second;
    }

    for (int i = 1; i <= seq_size; i++) {
        dp_lis[i] = MAX_L;
    }
    dp_lis[0] = 0;

    for (int i = 1; i <= seq_size; i++) {
        int lb = 0;
        int ub = seq_size;
        while(lb + 1 < ub) {
            int mid = (lb + ub) / 2;
            if (dp_lis[mid] < seq[i]) {
                lb = mid;
            } else {
                ub = mid;
            }
        }
        dp_lis[ub] = std::min(dp_lis[ub], seq[i]);
    }

    int length = 0;
    for (int i = 1; i <= seq_size; i++) {
        if (dp_lis[i] < MAX_L) {
            length++;
        } else {
            break;
        }
    }

    double PI = acos(-1.0);

    double ret = (x2 - x1 + y2 - y1) * 100.0;

    if (length == std::min(x2 - x1 + 1, y2 - y1 + 1)) {
        ret += (length - 1) * (5.0 * PI - 20.0);
        ret += 10.0 * PI - 20.0;
    } else {
        ret += length * (5.0 * PI - 20.0);
    }

    std::cout << std::setprecision(14) << ret << std::endl;

    return 0;
}

Submission Info

Compile Error

./Main.cpp:26:9: error: ‘int y1’ redeclared as different kind of symbol
 int x1, y1, x2, y2;
         ^
In file included from /usr/include/features.h:374:0,
                 from /usr/include/stdio.h:27,
                 from ./Main.cpp:1:
/usr/include/x86_64-linux-gnu/bits/mathcalls.h:241:1: note: previous declaration ‘double y1(double)’
 __MATHCALL (y1,, (_Mdouble_));
 ^
./Main.cpp: In function ‘int main(int, char**)’:
./Main.cpp:33:20: error: no match for ‘operator>>’ (operand types are ‘std::basic_istream<char>::__istream_type {aka std::basic_istream<char>}’ and ‘double(double) throw ()’)
     std::cin >> x1 >> y1 >> x2 >> y2;
                    ^
In file included from /usr/include/c++/5/fstream:38:0,
                 from ./Main.cpp:3:
/usr/include/c++/5/istream:120:7: note: candidate: std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(std::basic_istream<_CharT, _Traits>::__istream_type& (*)(std::basic_istream<_CharT, _Traits>::__istream_type&)) [with ...