oj.uz

Submission #892032

# Submission time Handle Problem Language Result Execution time Memory
892032 2023-12-24T17:29:14 Z DAleksa Fence (CEOI08_fence) C++17
100 / 100
 2 ms 348 KB 
#include <bits/stdc++.h>

using namespace std;

struct Point {
    int x;
    int y;
    Point() { x = 0; y = 0; }
    Point(int _x, int _y) { x = _x; y = _y; }
    Point operator - (Point A) { return Point(x - A.x, y - A.y); }
};
int sign(int x) { return (x > 0) - (x < 0); }
int cross(Point A, Point B) { return A.x * B.y - A.y * B.x; }
int cross(Point A, Point B, Point C) { return cross(B - A, C - A); }
int orientation(Point A, Point B, Point C) { return sign(cross(A, B, C)); }

const int N = 1e2 + 10;
int n, m;
vector<Point> a, b;
vector<int> g[N];

vector<Point> convex_hull(vector<Point> v) {
    if(v.size() <= 3) return v;
    sort(v.begin(), v.end(), [&](Point p1, Point p2) { return p1.x < p2.x; });
    vector<Point> up, down;
    for(Point p : v) {
        while(up.size() > 1 && orientation(up[up.size() - 2], up.back(), p) >= 0) up.pop_back();
        up.push_back(p);
        while(down.size() > 1 && orientation(down[down.size() - 2], down.back(), p) <= 0) down.pop_back();
        down.push_back(p);
    }
    up.pop_back();
    reverse(up.begin(), up.end());
    up.pop_back();
    for(Point p : up) down.push_back(p);
    return down;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    a.resize(n);
    b.resize(m);
    for(int i = 0; i < n; i++) cin >> a[i].x >> a[i].y;
    for(int i = 0; i < m; i++) cin >> b[i].x >> b[i].y;
    vector<Point> ch = convex_hull(a);
    vector<Point> nwb;
    for(int i = 0; i < m; i++) {
        bool in = true;
        for(int j = 0; j < ch.size(); j++) {
            if(orientation(ch[j], ch[(j + 1) % ch.size()], b[i]) <= 0) {
                in = false;
                break;
            }
        }
        if(in) nwb.push_back(b[i]);
    }
    b = nwb;
    int total = m;
    m = b.size();
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            bool left = false, right = false;
            for(int k = 0; k < m; k++) {
                if(orientation(a[i], a[j], b[k]) == 1) left = true;
                else if(orientation(a[i], a[j], b[k]) == -1) right = true;
            }
            if(left && right) continue;
            if(left) g[i].push_back(j);
            else if(right) g[j].push_back(i);
//            else assert(false);
        }
    }
//    for(int i = 0; i < n; i++) {
//        cout << i << ": ";
//        for(int j : g[i]) cout << j << " ";
//        cout << "\n";
//    }
//    return 0;
    int ans = (total - m) * 111;
    int mn = INT_MAX;
    for(int start = 0; start < n; start++) {
        queue<int> q;
        vector<int> dist(n, 1e9);
        vector<bool> mark(n, false);
        dist[start] = 0;
        q.push(start);
        mark[start] = true;
        while(!q.empty()) {
            int u = q.front();
            q.pop();
            for(int v : g[u]) {
                if(v == start) mn = min(mn, dist[u] + 1);
                if(mark[v]) continue;
                mark[v] = true;
                q.push(v);
                dist[v] = min(dist[v], dist[u] + 1);
            }
        }
    }
    if(mn == INT_MAX) mn = 0;
    cout << ans + 20 * mn;
    return 0;
}

Compilation message

fence.cpp: In function 'int main()':
fence.cpp:51:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for(int j = 0; j < ch.size(); j++) {
      |                        ~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct