#include<bits/stdc++.h>
#define breturn return
using namespace std;
vector<pair<int, int> > kor, dhull, ghull, hull, dot, gdot;
int n, m, a, b, mat[101][101], mi;
bool ccw(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
if(a.first * (b.second - c.second) + b.first * (c.second - a.second) + c.first * (a.second - b.second) < 0) breturn false;
else breturn true;
}
int main() {
cin >> n >> m;
for(int i = 0; i < n; i++) {
cin >> a >> b;
kor.push_back({a, b});
}
for(int i = 0; i < m; i++) {
cin >> a >> b;
dot.push_back({a, b});
}
sort(kor.begin(), kor.end());
for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) mat[i][j] = 1e9;
ghull.push_back(kor[0]), ghull.push_back(kor[1]), dhull.push_back(kor[0]), dhull.push_back(kor[1]);
for(int i = 2; i < n; i++) {
pair<int, int> x = kor[i];
if(!ccw(ghull[ghull.size() - 2], ghull[ghull.size() - 1], x)) ghull.push_back(x);
else ghull.pop_back(), ghull.push_back(x);
if(ccw(dhull[dhull.size() - 2], dhull[dhull.size() - 1], x)) dhull.push_back(x);
else dhull.pop_back(), dhull.push_back(x);
}
dhull.pop_back();
reverse(dhull.begin(), dhull.end());
for(int i = 0; i < ghull.size(); i++) hull.push_back(ghull[i]);
for(int i = 0; i < dhull.size(); i++) hull.push_back(dhull[i]);
//for(int i = 0; i < hull.size(); i++) cout << hull[i].first << " <-> " << hull[i].second << '\n';
for(int i = 0; i < dot.size(); i++) {
bool bad = false;
for(int j = 1; j < hull.size(); j++) bad += ccw(hull[j - 1], hull[j], dot[i]);
if(!bad) gdot.push_back(dot[i]);
}
for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(i != j) {
bool bad = false;
for(int k = 0; k < gdot.size(); k++) bad += !ccw(kor[i], kor[j], gdot[k]);
if(!bad) mat[i][j] = 1;
}
mi = (int)1e9;
for(int k = 0; k < n; k++) for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j]);
for(int i = 0; i < n; i++) mi = min(mi, mat[i][i]);
cout << (dot.size() - gdot.size()) * 111 + mi * 20;
}
Compilation message
fence.cpp: In function 'int main()':
fence.cpp:32:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for(int i = 0; i < ghull.size(); i++) hull.push_back(ghull[i]);
| ~~^~~~~~~~~~~~~~
fence.cpp:33:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for(int i = 0; i < dhull.size(); i++) hull.push_back(dhull[i]);
| ~~^~~~~~~~~~~~~~
fence.cpp:35:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for(int i = 0; i < dot.size(); i++) {
| ~~^~~~~~~~~~~~
fence.cpp:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for(int j = 1; j < hull.size(); j++) bad += ccw(hull[j - 1], hull[j], dot[i]);
| ~~^~~~~~~~~~~~~
fence.cpp:42:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(int k = 0; k < gdot.size(); k++) bad += !ccw(kor[i], kor[j], gdot[k]);
| ~~^~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
