oj.uz

Submission #348166

# Submission time Handle Problem Language Result Execution time Memory
348166 2021-01-14T10:06:14 Z jesus_coconut Fence (CEOI08_fence) C++17
100 / 100
 2 ms 364 KB 
#include <bits/stdc++.h>
#define all(a) begin(a), end(a)
#define x first
#define y second
using namespace std;



bool cw(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
    return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) < 0;
}

bool ccw(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
    return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) > 0;
}

map<pair<int, int>, int> name;

vector<pair<int, int>> v;
deque <pair<int ,int>> hull, hull2;

void construct_hull() {
    sort(all(v));
    for(auto p : v) {
        while(hull.size() > 1 && ccw(hull[hull.size() - 2], hull.back(), p) > 0)
            hull.pop_back();
        hull.push_back(p);
    }
    for(int i = v.size() - 1; i >= 0; --i) {
        pair<int, int> p = v[i];
        while(hull2.size() > 1 && ccw(hull2[hull2.size() - 2], hull2.back(), p) > 0)
            hull2.pop_back();
        hull2.push_back(p);
    }
    hull2.pop_front(); hull2.pop_back();
    for(auto x : hull2)
        hull.push_back(x);
    int cnt = 0;
    for(auto x : v)
        name[x] = cnt++;
}

bool inside(pair<int, int> p) {
    for (int i = 0; i < (int)hull.size(); ++i) {
        if (ccw(p, hull[i], hull[(i + 1) % hull.size()])) {
            return false;
        }
    }
    return true;
}

int const N = 110;

int mat[N][N];

int shortest_cycle() {
    int sol = 1e9;
    int n = v.size();
    for(int k = 0; k < n; ++k)
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j)
                if(mat[i][j] > mat[i][k] + mat[k][j])
                    mat[i][j] = mat[i][k] + mat[k][j];
    for(int i = 0; i < n; ++i)
        sol = min(sol, mat[i][i]);
    return sol;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    v.resize(n);
    for (auto &[a, b] : v) cin >> a >> b;
    construct_hull();
    vector<pair<int, int>> t;
    for (int i = 0; i < m; ++i) {
        pair<int, int> p;
        cin >> p.x >> p.y;
        if (inside(p)) {
            t.push_back(p);
        }
    }
    if (t.size() == 0) {
        cout << 111ll * m << '\n';
        return 0;
    }
    memset(mat, 0x3f, sizeof mat);
    for (auto i : v) {
        for (auto k : v) {
            if (i == k) continue;
            bool b = true;
            for (int j = 0; j < (int)t.size(); ++j) {
                if (ccw(i, k, t[j])) {
                    b = false;
                    break;
                }
            }
            if (b) {
                mat[name[i]][name[k]] = 1;
            }
        }
    }
    cout << 20ll * shortest_cycle() + 111ll * (m - t.size());
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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