#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;
else 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++) {
| ~~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 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 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
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 |
1 ms |
592 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
392 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
