#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define int long long
const int N = 110;
struct point {
int x, y;
};
vector<int> g[N];
vector<point> a(N), b(N);
int n, m, d[N], vis[N];
int cross(point a, point b, point c) {
point v1 = {b.x - a.x, b.y - a.y};
point v2 = {c.x - a.x, c.y - a.y};
return v2.x * v1.y - v2.y * v1.x;
}
vector<point> convex_hull(vector<point> c) {
sort(c.begin(), c.end(), [&](point a, point b) {
return make_pair(a.x, a.y) < make_pair(b.x, b.y);
});
vector<point> up, down;
for (int i = 0;i < n;i++) {
while (up.size() >= 2 && cross(up[up.size() - 2], c[i], up.back()) > 0)
up.pop_back();
up.push_back(c[i]);
}
for (int i = n - 1;i >= 0;i--) {
while (down.size() >= 2 && cross(down[down.size() - 2], c[i], down.back()) > 0)
down.pop_back();
down.push_back(c[i]);
}
vector<point> r = up;
for (int i = 1;i < (int)down.size() - 1;i++)
r.push_back(down[i]);
return r;
}
signed main() {
ios_base::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
//freopen("newbarn.in", "r", stdin);
//freopen(newbarn.out", "w", stdout);
int tt = 1;
//cin >> tt;
while (tt--) {
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;
//n->crveni
//m->zeleni
vector<point> ch = convex_hull(a);
vector<point> temp;
for (int i = 0;i < m;i++) {
int x = 1;
for (int j = 0;j < ch.size();j++) {
x &= (cross(ch[j], ch[(j + 1) % ch.size()], b[i]) > 0);
}
if (x > 0)
temp.push_back(b[i]);
}
int ans = 111 * (m - (int)temp.size());
b = temp;
for (int i = 0;i < n;i++) {
for (int j = i + 1;j < n;j++) {
int x = 1, y = 1;
for (auto p : b) {
x &= (cross(a[i], a[j], p) > 0);
y &= (cross(a[i], a[j], p) < 0);
}
if (x > 0)
g[i].push_back(j);
else if (y > 0)
g[j].push_back(i);
}
}
int mn = 1e18;
for (int i = 0;i < n;i++) {
queue<int> q;
q.push(i);
for (int j = 0;j < n;j++)
d[j] = 1e9, vis[j] = 0;
d[i] = 0;
vis[i] = 1;
while (!q.empty()) {
auto v = q.front();
q.pop();
for (auto u : g[v]) {
if (u == i)
mn = min(mn, d[v] + 1);
if (vis[u])
continue;
d[u] = min(d[u], d[v] + 1);
q.push(u);
vis[u] = 1;
}
}
}
if (mn == 1e18)
mn = 0;
cout << ans + 20 * mn;
}
return 0;
}
Compilation message
fence.cpp: In function 'int main()':
fence.cpp:60:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for (int j = 0;j < ch.size();j++) {
| ~~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
