#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;
//for(int i = 0; i < n; i++) mat[i][i] = 0;
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 < gdot.size(); i++) cout << gdot[i].first << " -> " << gdot[i].second << '\n';
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, mat[j][i] = 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++, cout << '\n') for(int j = 0; j < n; j++) cout << mat[i][j] << " ";
for(int i = 0; i < n; i++) mi = min(mi, mat[i][i]);
cout << (dot.size() - gdot.size()) * 111 + (mi + 1) * 20;
}
Compilation message
fence.cpp: In function 'int main()':
fence.cpp:34: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]
34 | for(int i = 0; i < ghull.size(); i++) hull.push_back(ghull[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 < dhull.size(); i++) hull.push_back(dhull[i]);
| ~~^~~~~~~~~~~~~~
fence.cpp:37: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]
37 | for(int i = 0; i < dot.size(); i++) {
| ~~^~~~~~~~~~~~
fence.cpp:39: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]
39 | for(int j = 1; j < hull.size(); j++) bad += ccw(hull[j - 1], hull[j], dot[i]);
| ~~^~~~~~~~~~~~~
fence.cpp:46: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]
46 | for(int k = 0; k < gdot.size(); k++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
