Submission #1541653

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <algorithm>
#include <functional>

using namespace std;

template <class T>
class segment_tree {
    public:
    segment_tree(int n, function<T(const T&, const T&)> func, const T& init = T());
    ~segment_tree();
    void update(int x, const T& value);
    T get(int x, int y) const; // [x, y)
    
    private:
    int size;
    function<T(const T&, const T&)> func;
    T init;
    T* data;
};

template <class T> segment_tree<T>::segment_tree(int n, function<T(const T&, const T&)> func, const T& init) : size(1 << (32 - __builtin_clz(n - 1))), func(func), init(init) {
    data = (T *)malloc(sizeof(T) * size * 2);
    for (int i = 0; i < size * 2; i++) data[i] = init;
}

template <class T> segment_tree<T>::~segment_tree() {
    free(data);
}

template <class T> void segment_tree<T>::update(int x, const T& value) {
    data[x += size] = value;
    while (x >>= 1) data[x] = func(data[x * 2], data[x * 2 + 1]);
}

template <class T> T segment_tree<T>::get(int x, int y) const {
    T vl = init, vr = init;
    for (x += size, y += size; x < y; x >>= 1, y >>= 1) {
        if (x & 1) vl = func(vl, data[x++]);
        if (y & 1) vr = func(data[--y], vr);
    }
    return func(vl, vr);
}

double pi = acos(-1);
int x[200002];
int y[200002];

int main() {
    int n, mc, i;
    double ans;
    map <int, int> mpx, mpy;
    map <int, int>::iterator it;
    
    scanf("%d %d %d %d", &x[0], &y[0], &x[1], &y[1]);
    scanf("%d", &n);
    
    for (i = 0; i < n; i++) scanf("%d %d", &x[i + 2], &y[i + 2]);
    
    ans = (long long)abs(x[0] - x[1]) * 100 + (long long)abs(y[0] - y[1]) * 100;
    mc = min(abs(x[0] - x[1]), abs(y[0] - y[1]));
    
    for (i = 0; i < n + 2; i++) {
        mpx[x[i]] = 0;
        mpy[y[i]] = 0;
    }
    
    for (it = mpx.begin(), i = 0; it != mpx.end(); it++, i++) it->second = i;
    for (it = mpy.begin(), i = 0; it != mpy.end(); it++, i++) it->second = i;
    
    for (i = 0; i < n + 2; i++) {
        x[i] = mpx[x[i]];
        y[i] = mpy[y[i]];
    }
    
    if (x[0] == x[1]) {
        if (y[0] > y[1]) swap(y[0], y[1]);
        
        for (i = 2; i < n + 2; i++) {
            if (x[i] == x[0] && y[i] > y[0] && y[i] < y[1]) {
                ans -= 20;
                ans += 10 * pi;
            }
        }
    } else if (y[0] == y[1]) {
        if (x[0] > x[1]) swap(x[0], x[1]);
        
        for (i = 2; i < n + 2; i++) {
            if (y[i] == y[0] && x[i] > x[0] && x[i] < x[1]) {
                ans -= 20;
                ans += 10 * pi;
            }
        }
    } else {
        int c;
        vector <pair<int, int> > v;
        
        if (x[0] > x[1]) {
            swap(x[0], x[1]);
            swap(y[0], y[1]);
        }
        
        if (y[0] > y[1]) {
            for (i = 1; i < n + 2; i++) y[i] = y[0] * 2 - y[i];
        }
        
        for (i = 2; i < n + 2; i++) v.push_back(make_pair(x[i], y[i]));
        
        sort(v.begin(), v.end());
        
        segment_tree<int> s(y[1] + 1, [](int a, int b) { return max(a, b);}, 0);
        
        for (i = 0; i < v.size(); i++) {
            int xx = v[i].first;
            int yy = v[i].second;
            
            if (xx < x[0] || xx > x[1] || yy < y[0] || yy > y[1]) continue;
            
            s.update(yy, s.get(y[0], yy) + 1);
        }
        
        c = s.get(y[0], y[1] + 1);
        
        if (c <= mc) {
            ans -= 20 * c;
            ans += 5 * pi * c;
        } else {
            ans -= 20 * mc;
            ans += 5 * pi * mc;
            ans -= 20;
            ans += 10 * pi;
        }
    }
    
    printf("%.12lf\n", ans);
    
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:59:53: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d", &x[0], &y[0], &x[1], &y[1]);
                                                     ^
./Main.cpp:60:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
./Main.cpp:62:65: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     for (i = 0; i < n; i++) scanf("%d %d", &x[i + 2], &y[i + 2]);
                                                                 ^

Judge Result