Submission #1208984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208984		urejgi	Demarcation (BOI14_demarcation)	C++17	100 / 100	124 ms	9672 KiB

demarcation

#pragma GCC optimize("O3,unroll-loops,fast-math")
#pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt,tune=native,fma")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const double EPS = 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;
    }
    friend bool operator<(const Point &a, const Point &b) {
        return (a.x < b.x || (abs(a.x - b.x) < EPS && a.y < b.y));
    }
    friend bool operator>(const Point &a, const Point &b) {
        return !(a < b);
    }
    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 < EPS;
    }
    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 < EPS);
    }
    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> P;
map<int,int> mp;
set<int> box, top;
vector<ll> per;

inline void calc(){
    for(int i = 0; i < n; i++){
        per[i] = abs(P[(i+1)%n].x - P[i].x) + abs(P[(i+1)%n].y - P[i].y);
        if(i) per[i] += per[i-1];
    }
}

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

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

bool check(int pi, int qi, int ext){
    pt p,q,pr,qr;
    ll cx;
    p = P[pi], q = P[qi];
    pr = P[right(pi)], qr = P[right(qi)];
    ll c_p, exc;
    if(pi > qi){
        c_p = per[n-1] - (pi ? per[pi-1] : 0);
        c_p += (qi ? per[qi-1] : 0);
    }else{
        c_p = per[qi-1] - (pi ? per[pi-1] : 0);
    }
    cx = per[n-1]/2 - c_p + p.x + q.x;
    if(cx&1) return 0;
    cx /= 2;
    if(cx < cur_x) return 0;
    if(ext && cx > min(pr.x, qr.x)) return 0;
    if(!ext && cx != cur_x) return 0;
    int a_sz = 0, b_sz = 0;
    vector<pt> a,b;
    if(cx == p.x){
        if(P[(pi+1)%n].x != p.x) a.push_back(p);
        if(P[(n+pi-1)%n].x != p.x) b.push_back(p);
        b.push_back(P[(n+pi-1)%n]);
    }else if(cx < pr.x){
        a.push_back(p);
        a.push_back(pt(cx,p.y));
        b.push_back(pt(cx,p.y));
        b.push_back(P[(n+pi-1)%n]);
    }else{
        a.push_back(p);
        a.push_back(pt(cx,p.y));
        if(P[(n+pi-2)%n].x != cx) b.push_back(P[(n+pi-1)%n]);
    }
    if(cx == q.x){
        if(P[(n+qi-1)%n].x != q.x) a.push_back(q);
        if(P[(qi+1)%n].x != q.x) b.push_back(q);
        b.push_back(P[(qi+1)%n]);
    }else if(cx < qr.x){
        a.push_back(q);
        a.push_back(pt(cx,q.y));
        b.push_back(pt(cx,q.y));
        b.push_back(P[(qi+1)%n]);
    }else{
        a.push_back(q);
        a.push_back(pt(cx,q.y));
        if(P[(qi+2)%n].x != cx) b.push_back(P[(qi+1)%n]);
    }
    a_sz = a.size();
    b_sz = b.size();
    if(pi < qi){
        a_sz += qi - pi - 1;
        b_sz += n - qi - 2;
        b_sz += pi-1;
    }else{
        a_sz += n - pi - 1;
        a_sz += qi;
        b_sz += pi - qi - 3;
    }
    if(a_sz != b_sz) return 0;
    if(pi < qi){
        for(int i = pi+1; i < qi; i++) a.push_back(P[i]);
        for(int i = qi+2; i < n; i++) b.push_back(P[i]);
        for(int i = 0; i < pi-1; i++) b.push_back(P[i]);
    }else{
        for(int i = pi+1; i < n; i++) a.push_back(P[i]);
        for(int i = 0; i < qi; i++) a.push_back(P[i]);
        for(int i = qi+2; i < pi-1; i++) b.push_back(P[i]);
    }
    if(a.size() != b.size())return 0;
    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 = cx;
                    ya = min(p.y, q.y);
                    yb = max(p.y, q.y);
                    return 1;
                }
            }
            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 = cx;
                    ya = min(p.y, q.y);
                    yb = max(p.y, q.y);
                    return 1;
                }
            }
            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 0;
}

bool is_vertical(){
    mp.clear();
    box.clear();
    top.clear();
    cur_x = -1;
    make_cw();
    calc();
    vector<pair<int,int>> todo;
    for(int i = 0; i < n; i++)
        if(P[i].x == P[(i+1)%n].x) todo.push_back(make_pair(i, (i+1)%n));
    sort(todo.begin(), todo.end(), [&](const auto&a, const auto&b){
        int x1 = P[a.first].x, y1 = P[a.first].y, x2 = P[b.first].x, 
                                                y2 = P[b.first].y;
        return x1 < x2 || (x1 == x2 && y1 < y2);
    });
    pair<int,int> prev_p = {-1, -1};
    pt p,q,pr,qr;
    int prev = -1, tp, d, ti, bi, is_top;
    set<int>::iterator it;
    vector<int> to_check;
    for(auto[pi,qi]:todo){
        p = P[pi], q = P[qi];
        if(p.y > q.y) swap(p,q), swap(pi,qi);
        if(p.x != cur_x){
            for(int y:to_check){
                if(box.find(y) != box.end()){
                    it = box.find(y);
                    is_top = (top.find(y) != top.end());
                    if(is_top){
                        ti = mp[y];
                        --it;
                        bi = mp[*it];
                    }else{
                        bi = mp[y];
                        ++it;
                        ti = mp[*it];
                    }
                    if(prev_p != make_pair(ti, bi)){
                        prev_p = make_pair(ti,bi);
                        if(ti <= bi) d = bi-ti+1;
                        else d = n-ti+bi+1;
                        if(n/2 - 4 > d || d > n/2+4) continue;
                        if(check(ti, bi, 1)) return 1;
                    }
                }
            }
            cur_x = p.x;
            to_check.clear();
            prev = -1;
        }
        pr = P[right(pi)];
        qr = P[right(qi)];
        if(pi <= prev) d = prev-pi+1;
        else d = n-pi+prev+1;
        if(prev != -1) if(n/2 - 4 <= d && d <= n/2+4 && check(pi, prev, 0)) return 1;
        prev = qi;
        prev_p = {-1, -1};
        tp = 0;
        if(p.x < pr.x){
            tp ^= 1;
            box.insert(p.y);
            mp[p.y] = pi;
            to_check.push_back(p.y);
        }else{
            box.erase(p.y);
            it = box.lower_bound(p.y);
            if(it != box.begin()) to_check.push_back(*(--it));
        }
        if(q.x < qr.x){
            tp ^= 2;
            box.insert(q.y);
            mp[q.y] = qi;
            to_check.push_back(q.y);
        }else{
            box.erase(q.y);
            it = box.lower_bound(q.y);
            if(it != box.end()) to_check.push_back(*it);
        }
        if(tp == 1){
            if(top.find(q.y) != top.end()){
                top.erase(q.y);
                top.insert(p.y);
            }
        }else if(tp == 2){
            if(top.find(p.y) != top.end()){
                top.erase(p.y);
                top.insert(q.y);
            }
        }else if(tp == 3){
            it = box.find(p.y);
            if(it != box.begin()){
                auto prev_it = it;
                --prev_it;
                if (top.find(*prev_it) == top.end()) 
                    top.insert(p.y);
                else top.insert(q.y);
            } else {
                top.insert(q.y);
            }
        }
    }
    return 0;
}

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

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    solve();
    return 0;
}

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