#include <bits/stdc++.h>
using namespace std;
struct pt {
int x;
int y;
};
bool operator == (pt a, pt b) {
return a.x == b.x && a.y == b.y;
}
bool operator < (pt a, pt b) {
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
int orient(pt a, pt b, pt c) {
int val = (b.y - a.y) * (c.x - b.x)
- (b.x - a.x) * (c.y - b.y);
if (val == 0) {
return 0;
}
return val > 0 ? 1 : 2; // cw, ccw
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<pt> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i].x >> a[i].y;
}
vector<pt> b(m);
for (int i = 0; i < m; i++) {
cin >> b[i].x >> b[i].y;
}
vector<pt> up;
vector<pt> down;
{
sort(a.begin(), a.end(), [&](pt p, pt q) {
if (p.x != q.x) {
return p.x < q.x;
} else {
return p.y < q.y;
}
});
for (int i = 0; i < n; i++) {
while (up.size() >= 2 && orient(up[up.size() - 2], up.back(), a[i]) == 2) {
up.pop_back();
}
up.push_back(a[i]);
}
}
{
sort(a.begin(), a.end(), [&](pt p, pt q) {
if (p.x != q.x) {
return p.x > q.x;
} else {
return p.y > q.y;
}
});
for (int i = 0; i < n; i++) {
while (down.size() >= 2 && orient(down[down.size() - 2], down.back(), a[i]) == 2) {
down.pop_back();
}
down.push_back(a[i]);
}
}
set<pt> was;
vector<pt> hull;
for (pt p : up) {
if (was.find(p) == was.end()) {
was.insert(p);
hull.push_back(p);
}
}
for (pt p : down) {
if (was.find(p) == was.end()) {
was.insert(p);
hull.push_back(p);
}
}
vector<pt> new_b;
for (int i = 0; i < m; i++) {
bool ok = true;
for (int j = 0; j < hull.size(); j++) {
if (orient(hull[j], hull[(j + 1) % hull.size()], b[i]) != 1) {
ok = false;
}
}
if (ok) {
new_b.push_back(b[i]);
}
}
int left = m - (int) new_b.size();
b = new_b;
m = (int) b.size();
vector<vector<int>> g(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
continue;
}
bool ok = true;
for (int k = 0; k < m; k++) {
if (orient(a[i], a[j], b[k]) != 1) {
ok = false;
}
}
if (ok) {
g[i].push_back(j);
}
}
}
if (m == 0) {
cout << left * 111 << '\n';
return 0;
}
const int inf = (int) 1e9;
int ans = inf;
for (int s = 0; s < n; s++) {
vector<int> dist(n, -1);
dist[s] = 0;
vector<int> que(1, s);
int mn = inf;
for (int b = 0; b < (int) que.size(); b++) {
int i = que[b];
for (int j : g[i]) {
if (dist[j] == -1) {
dist[j] = dist[i] + 1;
que.push_back(j);
} else if (j == s) {
mn = min(mn, dist[i] + 1);
}
}
}
if (mn != inf) {
ans = min(ans, mn * 20 + left * 111);
}
}
cout << ans << '\n';
return 0;
}
Compilation message
fence.cpp: In function 'int main()':
fence.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for (int j = 0; j < hull.size(); j++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
