제출 #1120906

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1120906		PVSekhar	경계 (BOI14_demarcation)	C++14	0 / 100	9 ms	1596 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;
set<pair<ll, ll>> 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]);
}

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

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(make_pair(p.y, h));
        up_is_out.erase(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) {
    ll excess = peri - find_d(a, b) - abs(poly[a].x - poly[b].x), h_x, changed = 0;
    if (excess < 0 || (excess % 2)) return false;
    excess /= 2;
    needed = max(poly[a].x, poly[b].x) + excess;
    h_x = poly[find_h(a)].x;
    if (h_x < needed) return false;
    else if (h_x == needed) a = find_h(a), changed++;
    h_x = poly[find_h(b)].x;
    if (h_x < needed) return false;
    else if (h_x == needed) b = find_h(b), changed++;
    return true;
}

bool compare(vector<Pt> p1, vector<Pt> p2) {
    sort(p1.begin(), p1.end());
    vector<Pt> poly;
    for (int i = 0; i < 2; i++) {
        for (int j = -1; j < 2; j += 2) {
            for (int k = -1; k < 2; k += 2) {
                poly = transform(p2, p2.size(), i, j, k);
                sort(poly.begin(), poly.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 - poly[it].x;
                    else if (x_d != p1[it].x - poly[it].x) flag = 0;
                    if (y_d == INF) y_d = p1[it].y - poly[it].y;
                    else if (y_d != p1[it].y - poly[it].y) flag = 0;
                }
                if (flag) return 1;
            }
        }
    }
    return 0;
}

bool check(ll &a, ll &b, ll &x, ll &y1, ll &y2) {
    vector<Pt> p1, p2;
    ll needed;
    y1 = poly[b].y;
    y2 = poly[a].y;
    if (precheck(a, b, needed)) {
        x = needed;
        if (a < b) {
            for (int i = a + 1; i < b; i++) p1.push_back(poly[i]);
            for (int i = 0; i < a; i++) p2.push_back(poly[i]);
            for (int i = b + 1; i < n; 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));
        p2.push_back(Pt(x, y1, n + 1));
        p2.push_back(Pt(x, y2, n + 2));
        if (p1.size() == p2.size() && compare(p1, p2)) return true;
    }
    return false;
}

bool check_vertical(ll &x, ll &y1, ll &y2) {
    for (int i = 0; i < n; i++) poly[i].ind = i;
    view.clear();
    up_is_out.clear();
    pre_dist.resize(n);
    vector<Pt> pts;
    for (int i = 0; i < n; i++) pts.push_back(poly[i]);
    sort(pts.begin(), pts.end());
    comp_pre_dist();
    for (int i = 0; i < n; i += 2) {
        add(pts[i]);
        add(pts[i + 1]);
        ll a, b;
        auto it = lower_bound(view.begin(), view.end(), make_pair(pts[i].y, pts[i].ind));
        if (it != view.begin() && it != view.end()) {
            a = (*it).second;
            b = (*(--it)).second;
            if (up_is_out.find((*it).first) == up_is_out.end() 
                && check(a, b, x, y1, y2)) return true;
        }
        it = lower_bound(view.begin(), view.end(), make_pair(pts[i + 1].y, pts[i + 1].ind));
        if (it != view.begin() && it != view.end()) {
            a = (*it).second;
            b = (*(--it)).second;
            if (up_is_out.find((*it).first) == up_is_out.end() 
                && check(a, b, x, y1, y2)) return true;
        }
        it = lower_bound(view.begin(), view.end(), make_pair(pts[i + 1].y, pts[i + 1].ind));
        if (it != view.end()) it++;
        if (it != view.begin() && it != view.end()) {
            a = (*it).second;
            b = (*(--it)).second;
            if (up_is_out.find((*it).first) == up_is_out.end() 
                && check(a, b, x, y1, y2)) return true;
        }
    }
    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 {
        poly = transform(poly, n, 1, 1, 1);
        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;
}

컴파일 시 표준 에러 (stderr) 메시지

demarcation.cpp: In function 'bool compare(std::vector<Pt>, std::vector<Pt>)':
demarcation.cpp:113:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |                 for (int it = 0; it < p1.size(); it++) {
      |                                  ~~~^~~~~~~~~~~

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