#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
const int maxn = 105;
int ccw(int ax, int ay, int bx, int by, int cx, int cy){
return ax * (by - cy) + bx * (cy - ay) + cx * (ay - by);
}
int fx[maxn];
int fy[maxn];
int tx[maxn];
int ty[maxn];
int ccwf(int a, int b, int c){
return fx[a] * (fy[b] - fy[c]) + fx[b] * (fy[c] - fy[a]) + fx[c] * (fy[a] - fy[b]);
}
const int inf = 10000000;
int mat[maxn][maxn];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
map<pair<int, int>, int> mapa;
vector<int> ind;
vector<int> gh;
vector<int> dh;
vector<int> hull;
for (int i = 1; i <= n; i++){
cin >> fx[i] >> fy[i];
if (mapa[make_pair(fx[i], fy[i])] == 0){
mapa[make_pair(fx[i], fy[i])] = i;
}
}
for (int i = 1; i <= m; i++){
cin >> tx[i] >> ty[i];
}
for (auto it: mapa){
ind.push_back(it.second);
}
for (int i = 0; i < ind.size(); i++){
while (gh.size() >= 2 && ccwf(gh[(int)gh.size() - 2], gh[(int)gh.size() - 1], ind[i]) > 0){
gh.pop_back();
}
gh.push_back(ind[i]);
}
gh.pop_back();
reverse(ind.begin(), ind.end());
for (int i = 0; i < ind.size(); i++){
while (dh.size() >= 2 && ccwf(dh[(int)dh.size() - 2], dh[(int)dh.size() - 1], ind[i]) > 0){
dh.pop_back();
}
dh.push_back(ind[i]);
}
dh.pop_back();
for (int i = 0; i < gh.size(); i++){
hull.push_back(gh[i]);
}
for (int i = 0; i < dh.size(); i++){
hull.push_back(dh[i]);
}
/*for (int i = 0; i < hull.size(); i++){
cout << hull[i] << " ";
}
cout << "\n";*/
vector<int> dt;
for (int i = 1; i <= m; i++){
int r = 0;
//cout << "I " << i << "\n";
int t = hull[(int)hull.size() - 1], t2 = hull[0];
if (ccw(fx[t], fy[t], tx[i], ty[i], fx[t2], fy[t2]) < 0){
r = 1;
}
//cout << r << "\n";
for (int j = 0; j < (int)hull.size() - 1; j++){
int t = hull[j];
int t2 = hull[j + 1];
if (ccw(fx[t], fy[t], tx[i], ty[i], fx[t2], fy[t2]) < 0){
r = 1;
}
//cout << r << "\n";
}
if (r == 0){
dt.push_back(i);
}
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
mat[i][j] = inf;
}
}
for (int i = 1; i <= n - 1; i++){
for (int j = i + 1; j <= n; j++){
int a = i;
int b = j;
int r = 0;
for (int k = 0; k < dt.size(); k++){
if (ccw(fx[a], fy[a], tx[dt[k]], ty[dt[k]], fx[b], fy[b]) > 0){
r = 1;
}
}
if (r == 0){
mat[a][b] = 1;
}
r = 0; a = j; b = i;
for (int k = 0; k < dt.size(); k++){
if (ccw(fx[a], fy[a], tx[dt[k]], ty[dt[k]], fx[b], fy[b]) > 0){
r = 1;
}
}
if (r == 0){
mat[a][b] = 1;
}
}
}
for (int k = 1; k <= n; k++){
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
if (mat[i][k] + mat[k][j] < mat[i][j]){
mat[i][j] = mat[i][k] + mat[k][j];
}
}
}
}
int sol = inf;
for (int i = 1; i <= n; i++){
sol = min(sol, mat[i][i]);
}
//cout << dt.size() << endl;
//cout << sol << " " << (m - (int)dt.size()) << endl;
if (dt.size() == 0){
cout << m * 111 << "\n";
}
else {
cout << 20 * sol + 111 * (m - (int)dt.size());
}
}
Compilation message
fence.cpp: In function 'int main()':
fence.cpp:55:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for (int i = 0; i < ind.size(); i++){
| ~~^~~~~~~~~~~~
fence.cpp:64:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for (int i = 0; i < ind.size(); i++){
| ~~^~~~~~~~~~~~
fence.cpp:72:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for (int i = 0; i < gh.size(); i++){
| ~~^~~~~~~~~~~
fence.cpp:75:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for (int i = 0; i < dh.size(); i++){
| ~~^~~~~~~~~~~
fence.cpp:116:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for (int k = 0; k < dt.size(); k++){
| ~~^~~~~~~~~~~
fence.cpp:126:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | for (int k = 0; k < dt.size(); k++){
| ~~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
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 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
508 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
