Submission #1122777

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122777		PVSekhar	Demarcation (BOI14_demarcation)	C++17	50 / 100	1095 ms	10128 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 = 2e5 + 2;
const ll INF = 2e9 + 2;

struct Pt{
    ll x, y, ind;

    Pt(const ll &x_ = 0, const ll &y_ = 0, const ll &ind_ = 0) : x(x_), y(y_), ind(ind_) {}
    friend bool operator< (const Pt &p, const Pt &q) {
        return p.ind != q.ind && (p.x < q.x || (p.x == q.x && p.y < q.y));
    }
    friend bool operator== (const Pt &p, const Pt &q) {
        return p.ind == q.ind;
    }
    friend std::istream &operator>>(std::istream &is, Pt &p) {
        return is >> p.x >> p.y;
    }
    friend std::ostream &operator<<(std::ostream &os, const Pt &p) {
        return os << "(" << p.x << ", " << p.y << ")";
    }
};

ll peri = 0, n, cur_x, solved = 0;
set<pair<ll, ll>> ab_check, view; // y, poly ind
set<ll> up_is_out; // for which y, in current view, above which is out of the polygon
vector<Pt> poly;
vector<ll> pre_dist;

void clockwise(vector<Pt> &poly, ll n) {
    ll lm = -1;
    for (int i = 0; i < n; i++) {
        if (lm == -1 || poly[i] < poly[lm]) lm = i;
    }
    if (poly[(lm + 1) % n].y != poly[lm].y) reverse(poly.begin(), poly.end());
    vector<Pt> temp = poly;
    poly.clear();
    for (int i = n - 1 - lm; i < n; i++) poly.push_back(temp[i]);
    for (int i = 0; i < n - 1 - lm; i++) poly.push_back(temp[i]);
}

void transform(vector<Pt> &poly, ll n, ll swap_xy, ll mx, ll my) {
    for (int i = 0; i < n; i++) {
        poly[i].x *= mx, poly[i].y *= my;
    }
    if (swap_xy) {
        for (int i = 0; i < n; i++) {
            swap(poly[i].x, poly[i].y);
        }
    }
}

ll find_d(int a, int b) {
    if (a < b) return pre_dist[b - 1] - (a ? pre_dist[a - 1] : 0);
    return pre_dist[n - 1] - pre_dist[a - 1] + (b ? pre_dist[b - 1] : 0);
}

int find_h(int ind) {
    ll h = (ind + 1) % n; // hrizontal neighbour
    if (poly[h].x == poly[ind].x) h = (n + ind - 1) % n;
    return h;
}

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

void add(Pt &p){
    ll h = find_h(p.ind);
    if (poly[h].x < p.x) {
        view.erase(view.find(make_pair(p.y, h)));
        if (up_is_out.find(p.y) != up_is_out.end()) up_is_out.erase(up_is_out.find(p.y));
    } else {
        view.insert(make_pair(p.y, p.ind));
        auto it = view.find(make_pair(p.y, p.ind));
        if (it == view.begin()) return;
        it--;
        if (up_is_out.find((*it).first) == up_is_out.end()) up_is_out.insert(p.y);
    }
}

bool precheck(ll &a, ll &b, ll &needed) {
    // cout << a << " " << b << "\n";
    ll excess = peri - find_d(a, b) - abs(poly[a].x - poly[b].x), h_x;
    if (excess < 0 || (excess % 2)) return false;
    excess /= 2;
    needed = max(poly[a].x, poly[b].x) + excess;
    if (excess == 0) return true;
    h_x = poly[find_h(a)].x;
    if (h_x < needed) return false;
    else if (h_x == needed) a = find_h(a);
    h_x = poly[find_h(b)].x;
    if (h_x < needed) return false;
    else if (h_x == needed) b = find_h(b);
    ll c1 = 0, c2 = 0, x = needed;
    if (a < b) {
        c1 = b - a - 1;
        c2 = n - b + a - 1;
    } else {
        c1 = n - a + b - 1;
        c2 = a - b - 1;
    }
    if (poly[b].x != x) c1 += 2;
    else if (c1 && poly[(n + b - 1) % n].x != x) c1++;
    if (poly[a].x != x) c1 += 2;
    else if (c1 && poly[(a + 1) % n].x != x) c1++;
    if (poly[(n + a - 1) % n].x != x) c2++;
    if (poly[(b + 1) % n].x != x) c2++;
    if (c1 != c2) return false;
    return true;
}

bool compare(vector<Pt> &p1, vector<Pt> &p2) {
    sort(p1.begin(), p1.end());
    ll swapped = 0, m_x = 1, m_y = 1, c_x = 1, c_y = 1;
    for (int i = 0; i < 2; i++) {
        for (int j = -1; j < 2; j += 2) {
            for (int k = -1; k < 2; k += 2) {
                if (c_x != j) m_x = -1, c_x = j;
                else m_x = 1;
                if (c_y != k) m_y = -1, c_y = k;
                else m_y = 1;
                if (i && !swapped) {
                    swapped = 1;
                    transform(p2, p2.size(), 1, m_x, m_y);
                } else {
                    transform(p2, p2.size(), 0, m_x, m_y);
                }
                sort(p2.begin(), p2.end());
                ll x_d = INF, y_d = INF, flag = 1;
                for (int it = 0; it < p1.size(); it++) {
                    if (x_d == INF) x_d = p1[it].x - p2[it].x;
                    else if (x_d != p1[it].x - p2[it].x) flag = 0;
                    if (y_d == INF) y_d = p1[it].y - p2[it].y;
                    else if (y_d != p1[it].y - p2[it].y) flag = 0;
                }
                if (flag) {
                    return 1;
                }
            }
        }
    }
    return 0;
}

bool check(ll &a, ll &b, ll &x, ll &y1, ll &y2) {
    // cout << a << " " << b << "\n";
    vector<Pt> p1, p2;
    y1 = poly[b].y;
    y2 = poly[a].y;
    if (a < b) {
        for (int i = a + 1; i < b; i++) p1.push_back(poly[i]);
        for (int i = b + 1; i < n; i++) p2.push_back(poly[i]);
        for (int i = 0; i < a; i++) p2.push_back(poly[i]);
    } else {
        for (int i = a + 1; i < n; i++) p1.push_back(poly[i]);
        for (int i = 0; i < b; i++) p1.push_back(poly[i]);
        for (int i = b + 1; i < a; i++) p2.push_back(poly[i]);
    }
    if (poly[b].x != x) {
        p1.push_back(poly[b]);
        p1.push_back(Pt(x, y1, n + 2));
    } else if (p1.size() && p1.back().x != x) p1.push_back(Pt(x, y1, n + 2));
    if (poly[a].x != x) {
        p1.push_back(poly[a]);
        p1.push_back(Pt(x, y2, n + 1));
    } else if (p1.size() && p1.front().x != x) p1.push_back(Pt(x, y2, n + 1));
    if (p2.back().x != x) p2.push_back(Pt(x, y2, n + 1));
    if (p2.front().x != x) p2.push_back(Pt(x, y1, n + 2));
    solved = 1;
    if (p1.size() == p2.size()) {
        if (compare(p1, p2)) return true;
    }
    return false;
}

bool check_y(ll y, ll &x, ll &y1, ll &y2) {
    ll a, b, _zero = 0;
    auto it = lower_bound(view.begin(), view.end(), make_pair(y, _zero));
    if (it != view.begin() && it != view.end()) {
        a = (*it).second;
        b = (*(--it)).second;
        if (abs(a - b) >= n / 2 - 3 && abs(a - b) <= n / 2 + 3 && up_is_out.find((*it).first) == up_is_out.end())
            ab_check.insert(make_pair(a, b));
    }
    it = lower_bound(view.begin(), view.end(), make_pair(y, _zero));
    if (it != view.end()) {
        it++;
        if (it != view.begin() && it != view.end()) {
            a = (*it).second;
            b = (*(--it)).second;
            if (abs(a - b) >= n / 2 - 3 && abs(a - b) <= n / 2 + 3 && up_is_out.find((*it).first) == up_is_out.end())
                ab_check.insert(make_pair(a, b));
        }
    }
    return false;
}

bool check_vertical(ll &x, ll &y1, ll &y2) {
    view.clear();
    up_is_out.clear();
    pre_dist.resize(n);
    vector<Pt> pts;
    for (int i = 0; i < n; i++) poly[i].ind = i;
    for (int i = 0; i < n; i++) pts.push_back(poly[i]);
    sort(pts.begin(), pts.end());
    comp_pre_dist();
    cur_x = pts[0].x;
    vector<pair<ll, ll>> to_check;
    for (int i = 0; i < n; i += 2) {
        if (pts[i].x != cur_x) {
            for (ll j = 0; j < to_check.size(); j += 2) {
                if (check_y(to_check[j].first, x, y1, y2)) return true;
                if (check_y(to_check[j + 1].first, x, y1, y2)) return true;
                if (j + 2 < to_check.size()) {
                    ll a = to_check[j + 2].second, b = to_check[j + 1].second;
                    if (abs(a - b) >= n / 2 - 3 && abs(a - b) <= n / 2 + 3) ab_check.insert(make_pair(a, b));
                } 
            }
            // if (solved) return false;
            to_check.clear();
            cur_x = pts[i].x;
        }
        add(pts[i]);
        add(pts[i + 1]);
        to_check.push_back(make_pair(pts[i].y, pts[i].ind));
        to_check.push_back(make_pair(pts[i + 1].y, pts[i + 1].ind));
    }
    for (ll j = 0; j < to_check.size(); j += 2) {
        if (check_y(to_check[j].first, x, y1, y2)) return true;
        if (check_y(to_check[j + 1].first, x, y1, y2)) return true;
        if (j + 2 < to_check.size()) {
            ll a = to_check[j + 2].second, b = to_check[j + 1].second;
            if (abs(a - b) >= n / 2 - 3 && abs(a - b) <= n / 2 + 3) ab_check.insert(make_pair(a, b));
        } 
    }
    ll a, b;
    for (auto p : ab_check) {
        a = p.first;
        b = p.second;
        if (precheck(a, b, x) && check(a, b, x, y1, y2)) return true;
    }
    ab_check.clear();
    return false;
}

void solve() {
    ll x, y1, y2;
    cin >> n;
    Pt p;
    for (int i = 0; i < n; i++) {
        cin >> p;
        p.ind = i;
        poly.push_back(p);
    }
    for (int i = 0; i < n; i++) {
        peri += abs(poly[i].x - poly[(i + 1) % n].x);
        peri += abs(poly[i].y - poly[(i + 1) % n].y);
    }
    peri /= 2;
    clockwise(poly, n);
    if (check_vertical(x, y1, y2)) {
        cout << x << " " << y1 << " " << x << " " << y2 << "\n";
    } else {
        transform(poly, n, 1, 1, 1);
        clockwise(poly, n);
        solved = 0;
        if (check_vertical(x, y1, y2)) {
            if (y1 > y2) swap(y1, y2);
            cout << y1 << " " << x << " " << y2 << " " << x << "\n";
        } else cout << "NO\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll t;
    t = 1;
    // cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}

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