# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
348262 |
2021-01-14T12:09:59 Z |
Lukap |
Fence (CEOI08_fence) |
C++14 |
|
2 ms |
364 KB |
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> point;
const int MAXN = 107;
const int INF = 1e9 + 7;
int n,m;
vector<point> ghull,dhull,hull;
vector<point> rupe,stabla,uzeta_stabla;
vector<pair<point,point>> uzeti_bridovi;
int E[MAXN][MAXN];
map<point,int> koja;
int ccw (point a, point b, point c) {
return a.first * (b.second - c.second) + b.first * (c.second - a.second) + c.first * (a.second - b.second);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++) {
int a,b;
cin >> a >> b;
rupe.push_back({a,b});
koja[rupe[i]] = i;
}
for (int i = 0; i < m; i++) {
int a,b;
cin >> a >> b;
stabla.push_back({a,b});
}
sort(rupe.begin(),rupe.end());
for (auto p: rupe) {
while(ghull.size() > 1 && ccw(ghull[ghull.size() - 2], ghull.back(), p) > 0) ghull.pop_back();
ghull.push_back(p);
}
reverse(rupe.begin(), rupe.end());
for (auto p: rupe) {
while(dhull.size() > 1 && ccw(dhull[dhull.size() - 2], dhull.back(), p) > 0) dhull.pop_back();
dhull.push_back(p);
}
ghull.pop_back();
dhull.pop_back();
for (auto i: ghull) hull.push_back(i);
for (auto i: dhull) hull.push_back(i);
for (auto i: stabla) {
for (int j = 0; j < hull.size(); j++){
if(j == 0 && ccw(hull[hull.size() - 1],i,hull[0]) < 0) break;
if(j > 0 && ccw(hull[j - 1],i,hull[j]) < 0) break;
if(j == hull.size() - 1) uzeta_stabla.push_back(i);
}
}
if(uzeta_stabla.size() == 0) {
cout << m * 111;
return 0;
}
if(uzeta_stabla.size() == 1) {
cout << (m - 1) * 111 + 60;
return 0;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) E[i][j] = INF;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(i == j) continue;
for (int k = 0; k < uzeta_stabla.size(); k++) {
if(ccw(rupe[i],uzeta_stabla[k],rupe[j]) < 0) break;
if(k == uzeta_stabla.size() -1){
uzeti_bridovi.push_back({rupe[i],rupe[j]});
E[koja[rupe[i]]][koja[rupe[j]]] = 1;
}
}
}
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(E[i][k] + E[k][j] < E[i][j]) {
E[i][j] = E[i][k] + E[k][j];
}
}
}
}
int ciklus = INF;
for (int i = 0; i < n; i++) {
ciklus = min(ciklus,E[i][i]);
}
cout << 20 * ciklus + (stabla.size() - uzeta_stabla.size()) * 111;
return 0;
}
Compilation message
fence.cpp: In function 'int main()':
fence.cpp:66:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for (int j = 0; j < hull.size(); j++){
| ~~^~~~~~~~~~~~~
fence.cpp:71:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | if(j == hull.size() - 1) uzeta_stabla.push_back(i);
| ~~^~~~~~~~~~~~~~~~~~
fence.cpp:93:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for (int k = 0; k < uzeta_stabla.size(); k++) {
| ~~^~~~~~~~~~~~~~~~~~~~~
fence.cpp:95:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | if(k == uzeta_stabla.size() -1){
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |