oj.uz

Submission #1121088

# Submission time Handle Problem Language Result Execution time Memory
1121088 2024-11-28T11:57:37 Z PVSekhar Demarcation (BOI14_demarcation) C++14
50 / 100
 500 ms 15080 KB 
#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;
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(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) {
    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);
    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;
    y1 = poly[b].y;
    y2 = poly[a].y;
    if (precheck(a, b, x)) {
        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));
        if (p1.size() == p2.size() && 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 (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(y, _zero));
    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;
}

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 (check(a, b, x, y1, y2)) return true;
                } 
            }
            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 (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;
}

Compilation message

demarcation.cpp: In function 'bool compare(std::vector<Pt>, std::vector<Pt>)':
demarcation.cpp:114:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |                 for (int it = 0; it < p1.size(); it++) {
      |                                  ~~~^~~~~~~~~~~
demarcation.cpp: In function 'bool check_vertical(long long int&, long long int&, long long int&)':
demarcation.cpp:191:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |             for (ll j = 0; j < to_check.size(); j += 2) {
      |                            ~~^~~~~~~~~~~~~~~~~
demarcation.cpp:194:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  194 |                 if (j + 2 < to_check.size()) {
      |                     ~~~~~~^~~~~~~~~~~~~~~~~
demarcation.cpp:207:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  207 |     for (ll j = 0; j < to_check.size(); j += 2) {
      |                    ~~^~~~~~~~~~~~~~~~~
demarcation.cpp:210:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  210 |         if (j + 2 < to_check.size()) {
      |             ~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2108 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 8 ms 1956 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 51 ms 15008 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 504 KB Output is correct
13 Correct 1 ms 340 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 508 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 504 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 456 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 352 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 504 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 508 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 460 KB Output is correct
23 Correct 1 ms 504 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 3 ms 596 KB Output is correct
33 Correct 2 ms 596 KB Output is correct
34 Correct 2 ms 596 KB Output is correct
35 Correct 1 ms 596 KB Output is correct
36 Correct 4 ms 596 KB Output is correct
37 Correct 3 ms 596 KB Output is correct
38 Correct 2 ms 596 KB Output is correct
39 Correct 2 ms 596 KB Output is correct

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2120 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 9 ms 1956 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 60 ms 15080 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 2 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 508 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 2 ms 596 KB Output is correct
36 Correct 2 ms 596 KB Output is correct
37 Correct 2 ms 596 KB Output is correct
38 Correct 2 ms 596 KB Output is correct
39 Correct 3 ms 596 KB Output is correct
40 Correct 3 ms 596 KB Output is correct
41 Correct 3 ms 596 KB Output is correct
42 Correct 3 ms 596 KB Output is correct
43 Correct 5 ms 852 KB Output is correct
44 Execution timed out 1098 ms 4616 KB Time limit exceeded
45 Halted 0 ms 0 KB -