| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 892114 |
2023-12-24T23:02:57 Z |
OAleksa |
Fence (CEOI08_fence) |
C++14 |
|
1 ms |
348 KB |
#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];
int n, m, d[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;
vector<point> a(n), b(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 cost = 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(ch[i], ch[j], p) > 0);
y &= (cross(ch[i], ch[j], p) < 0);
}
if (x > 0)
g[i].push_back(j);
else if (y > 0)
g[j].push_back(i);
}
}
int ans = 1e18;
for (int i = 0;i < n;i++) {
queue<int> q;
q.push(i);
for (int j = 0;j < n;j++)
d[j] = 1e9;
d[i] = 0;
while (!q.empty()) {
auto v = q.front();
q.pop();
for (auto u : g[v]) {
if (u == i) {
ans = min(ans, (d[v] + 1) * 20);
break;
}
else if (d[u] > d[v] + 1) {
d[u] = d[v] + 1;
q.push(u);
}
}
}
}
cout << ans + cost;
}
return 0;
}
Compilation message
fence.cpp: In function 'int main()':
fence.cpp:58:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for (int j = 0;j < ch.size();j++) {
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 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 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
