Submission #1126606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126606		PVSekhar	Demarcation (BOI14_demarcation)	C++17	50 / 100	1095 ms	9676 KiB

demarcation

#include <bits/stdc++.h>
using namespace std;
#define ll long long
// const ll MOD = 998244353;
const ll MOD = 1e9 + 7;
const ll N = 1e5 + 2;

// from jiangly's template
const double TOL = 1e-9;

template<class T>
struct Point {    
    T x;
    T y;
    Point(const T x_ = 0, const T y_ = 0) : x(x_), y(y_) {}

    template<class U>
    operator Point<U>() {
        return Point<U>(U(x), U(y));
    }
    Point &operator+=(const Point &p) & {
        x += p.x;
        y += p.y;
        return *this;
    }
    Point &operator-=(const Point &p) & {
        x -= p.x;
        y -= p.y;
        return *this;
    }
    Point &operator*=(const T &v) & {
        x *= v;
        y *= v;
        return *this;
    }
    Point &operator/=(const T &v) & {
        x /= v;
        y /= v;
        return *this;
    }
    Point operator-() const {
        return Point(-x, -y);
    }
    friend Point operator+(Point a, const Point &b) {
        return a += b;
    }
    friend Point operator-(Point a, const Point &b) {
        return a -= b;
    }
    friend Point operator*(Point a, const T &b) {
        return a *= b;
    }
    friend Point operator/(Point a, const T &b) {
        return a /= b;
    }
    friend Point operator*(const T &a, Point b) {
        return b *= a;
    }
    // w/o tolerance
    // friend bool operator<(const Point &a, const Point &b) {
    //     return a.x < b.x || (a.x == b.x && a.y < b.y);
    // }
    // w/ tolerance
    friend bool operator<(const Point &a, const Point &b) {
        return (a.x < b.x || (abs(a.x - b.x) < TOL && a.y < b.y));
    }
    friend bool operator>(const Point &a, const Point &b) {
        return !(a < b);
    }
    // without tolerance
    // friend bool operator==(const Point &a, const Point &b) {
    //     return a.x == b.x && a.y == b.y;
    // }
    // friend bool operator!=(const Point &a, const Point &b) {
    //     return !(a.x == b.x && a.y == b.y);
    // }


    // with tolerance
    friend bool operator==(const Point &a, const Point &b) {
        Point<T> p = a - b;
        T len = sqrt(p.x * p.x + p.y * p.y);
        return len < TOL;
    }
    friend bool operator!=(const Point &a, const Point &b) {
        Point<T> p = a - b;
        T len = sqrt(p.x * p.x + p.y * p.y);
        return !(len < TOL);
    }
    friend std::istream &operator>>(std::istream &is, Point &p) {
        return is >> p.x >> p.y;
    }
    friend std::ostream &operator<<(std::ostream &os, const Point &p) {
        return os << "(" << p.x << ", " << p.y << ")";
    }
};

using Pt = Point<int>;

int n, x, ya, yb, cur_x;
vector<Pt> poly;
map<int, int> y_ind;
set<int> sweep, top_out;
vector<ll> peri;

void comp_peri() {
    for (int i = 0; i < n; i++) {
        peri[i] = abs(poly[(i + 1) % n].x - poly[i].x + poly[(i + 1) % n].y - poly[i].y);
        if (i) peri[i] += peri[i - 1];
    }
}

void make_cw() {
    int lm = -1;
    for (int i = 0; i < n; i++) if (lm == -1 || poly[i] < poly[lm]) lm = i;
    if (poly[lm].y != poly[(lm + 1) % n].y) {
        rotate(poly.begin(), poly.begin() + (lm + 1) % n, poly.end());
        reverse(poly.begin(), poly.end());
    } else {
        rotate(poly.begin(), poly.begin() + lm, poly.end());
    }
}

int right(int ind) {
    return poly[ind].y == poly[(ind + 1) % n].y ? (ind + 1) % n : (n + ind - 1) % n;
}

bool check(int p_ind, int q_ind, int extend) {
    Pt p, q, p_r, q_r;
    ll c_x;
    p = poly[p_ind], q = poly[q_ind];
    // cout << p << " " << q << "\n";
    p_r = poly[right(p_ind)], q_r = poly[right(q_ind)];
    ll c_peri, excess;
    if (p_ind > q_ind) {
        c_peri = peri[n - 1] - (p_ind ? peri[p_ind - 1] : 0);
        c_peri += (q_ind ? peri[q_ind - 1] : 0);
    } else {
        c_peri = peri[q_ind - 1] - (p_ind ? peri[p_ind - 1] : 0);
    }
    c_x = peri[n - 1] / 2 - c_peri + p.x + q.x;
    if (c_x % 2) return false;
    // cout << peri[n - 1] / 2 << " " << -c_peri << " " << p.x + q.x << "\n";
    c_x = c_x / 2;
    // cout << c_x << "\n";
    if (c_x < cur_x) return false;
    if (extend && c_x > min(p_r.x, q_r.x)) return false;
    if (!extend && c_x != cur_x) return false;
    vector<Pt> a, b;
    if (c_x == p.x) {
        if (poly[(p_ind + 1) % n].x != p.x) a.push_back(p);
        if (poly[(n + p_ind - 1) % n].x != p.x) b.push_back(p);
        b.push_back(poly[(n + p_ind - 1) % n]);
    } else if (c_x < p_r.x) {
        a.push_back(p);
        a.push_back(Pt(c_x, p.y));
        b.push_back(Pt(c_x, p.y));
        b.push_back(poly[(n + p_ind - 1) % n]);
    } else {
        a.push_back(p);
        a.push_back(Pt(c_x, p.y));
        if (poly[(n + p_ind - 2) % n].x != c_x) b.push_back(poly[(n + p_ind - 1) % n]);
    }
    if (c_x == q.x) {
        if (poly[(n + q_ind - 1) % n].x != q.x) a.push_back(q);
        if (poly[(q_ind + 1) % n].x != p.x) b.push_back(q);
        b.push_back(poly[(q_ind + 1) % n]);
    } else if (c_x < q_r.x) {
        a.push_back(q);
        a.push_back(Pt(c_x, q.y));
        b.push_back(Pt(c_x, q.y));
        b.push_back(poly[(q_ind + 1) % n]);
    } else {
        a.push_back(q);
        a.push_back(Pt(c_x, q.y));
        if (poly[(q_ind + 2) % n].x != c_x) b.push_back(poly[(q_ind + 1) % n]);
    }
    if (p_ind < q_ind) {
        for (int i = p_ind + 1; i < q_ind; i++) a.push_back(poly[i]);
        for (int i = q_ind + 2; i < n; i++) b.push_back(poly[i]);
        for (int i = 0; i < p_ind - 1; i++) b.push_back(poly[i]);
    } else {
        for (int i = p_ind + 1; i < n; i++) a.push_back(poly[i]);
        for (int i = 0; i < q_ind; i++) a.push_back(poly[i]);
        for (int i = q_ind + 2; i < p_ind - 1; i++) b.push_back(poly[i]);
    }
    if (a.size() != b.size()) return false;
    sort(a.begin(), a.end());
    ll dx, dy;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            dx = dy = 2e9;
            if (i) for (int k = 0; k < b.size(); k++) b[k].x *= -1;
            if (j) for (int k = 0; k < b.size(); k++) b[k].y *= -1;
            sort(b.begin(), b.end());
            for (int k = 0; k < b.size(); k++) {
                if (dx != 2e9 && dx != a[k].x - b[k].x) break;
                dx = a[k].x - b[k].x;
                if (dy != 2e9 && dy != a[k].y - b[k].y) break;
                dy = a[k].y - b[k].y;
                if (k == b.size() - 1) {
                    x = c_x;
                    ya = min(p.y, q.y);
                    yb = max(p.y, q.y);
                    return true;
                }
            }
            if (i) for (int k = 0; k < b.size(); k++) b[k].x *= -1;
            if (j) for (int k = 0; k < b.size(); k++) b[k].y *= -1;
        }
    }
    for (int k = 0; k < b.size(); k++) swap(b[k].x, b[k].y);
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            dx = dy = 2e9;
            if (i) for (int k = 0; k < b.size(); k++) b[k].x *= -1;
            if (j) for (int k = 0; k < b.size(); k++) b[k].y *= -1;
            sort(b.begin(), b.end());
            for (int k = 0; k < b.size(); k++) {
                if (dx != 2e9 && dx != a[k].x - b[k].x) break;
                dx = a[k].x - b[k].x;
                if (dy != 2e9 && dy != a[k].y - b[k].y) break;
                dy = a[k].y - b[k].y;
                if (k == b.size() - 1) {
                    x = c_x;
                    ya = min(p.y, q.y);
                    yb = max(p.y, q.y);
                    return true;
                }
            }
            if (i) for (int k = 0; k < b.size(); k++) b[k].x *= -1;
            if (j) for (int k = 0; k < b.size(); k++) b[k].y *= -1;
        }
    }
    return false;
}

bool is_vertical() {
    y_ind.clear();
    sweep.clear();
    top_out.clear();
    cur_x = -1;
    make_cw();
    comp_peri();
    vector<pair<int, int>> to_sweep;
    for (int i = 0; i < n; i++) {
        if (poly[i].x == poly[(i + 1) % n].x) to_sweep.push_back(make_pair(i, (i + 1) % n));
    }
    sort(to_sweep.begin(), to_sweep.end(), [&](const pair<int, int> &a, const pair<int, int> &b) {
        int x1 = poly[a.first].x, y1 = poly[a.first].y, x2 = poly[b.first].x, y2 = poly[b.first].y;
        return x1 < x2 || (x1 == x2 && y1 < y2);
    });
    pair<int, int> p_ind, q_ind, prev_p = make_pair(-1, -1);
    Pt p, q, p_r, q_r;
    int prev = -1, type, d, t_ind, b_ind, is_top;
    set<int>::iterator it;
    vector<int> to_check;
    for (auto [p_ind, q_ind] : to_sweep) {
        p = poly[p_ind], q = poly[q_ind];
        if (p.y > q.y) swap(p, q), swap(p_ind, q_ind);
        if (p.x != cur_x) {
            for (int y : to_check) {
                if (sweep.find(y) != sweep.end()) {
                    it = sweep.find(y);
                    is_top = (top_out.find(y) != top_out.end());
                    if (is_top) {
                        t_ind = y_ind[y];
                        b_ind = y_ind[*(--it)];
                    } else {
                        b_ind = y_ind[y];
                        t_ind = y_ind[*(++it)];
                    }
                    if (prev_p != make_pair(t_ind, b_ind)) {
                        prev_p = make_pair(t_ind, b_ind);
                        if (t_ind <= b_ind) d = b_ind - t_ind + 1;
                        else d = n - t_ind + b_ind + 1;
                        if (n/2 - 4 > d || d > n/2 + 4) continue;
                        if (check(t_ind, b_ind, 1)) return true;
                    }
                }
            }
            cur_x = p.x;
            to_check.clear();
            prev = -1;
        }
        p_r = poly[right(p_ind)];
        q_r = poly[right(q_ind)];
        if (p_ind <= prev) d = prev - p_ind + 1;
        else d = n - p_ind + prev + 1;
        if (prev != -1) if (n/2 - 4 <= d && d <= n/2 + 4 && check(p_ind, prev, 0)) return true;
        prev = q_ind;
        prev_p = make_pair(-1, -1);
        type = 0;
        if (p.x < p_r.x) {
            type ^= 1;
            sweep.insert(p.y);
            y_ind[p.y] = p_ind;
            to_check.push_back(p.y);
        } else {
            sweep.erase(p.y);
            it = sweep.lower_bound(p.y);
            if (it != sweep.begin()) to_check.push_back(*(--it));
        }
        if (q.x < q_r.x) {
            type ^= 2;
            sweep.insert(q.y);
            y_ind[q.y] = q_ind;
            to_check.push_back(q.y);
        } else {
            sweep.erase(q.y);
            it = sweep.lower_bound(q.y);
            if (it != sweep.end()) to_check.push_back(*it);
        }
        if (type == 1) {
            if (top_out.find(q.y) != top_out.end()) {
                top_out.erase(q.y);
                top_out.insert(p.y);
            }
        } else if (type == 2) {
            if (top_out.find(p.y) != top_out.end()) {
                top_out.erase(p.y);
                top_out.insert(q.y);
            }
        } else if (type == 3) {
            it = sweep.find(p.y);
            if (it != sweep.begin() && top_out.find(*(--it)) == top_out.end()) top_out.insert(p.y);
            else top_out.insert(q.y);
        }
    }
    return false;
}

void solve() {
    cin >> n;
    poly.resize(n);
    peri.resize(n);
    for (int i = 0; i < n; i++) cin >> poly[i];
    if (is_vertical()) {
        cout << x << " " << ya << " " << x << " " << yb << "\n";
    } else {
        for (int i = 0; i < n; i++) swap(poly[i].x, poly[i].y);
        if (is_vertical()) {
            cout << ya << " " << x << " " << yb << " " << x << "\n";
        } else cout << "NO\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    solve();
    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 23 / 23
• Subtask 4: 0 / 50