| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 348238 |
2021-01-14T11:40:59 Z |
saral |
Fence (CEOI08_fence) |
C++14 |
|
6 ms |
4460 KB |
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
const int N = 1010;
int t, n, m, a, b;
const int INF = 1e5;
vector<pair<pair<int, int>, int> > holes, trees;
vector<pair<int, int> > holesOG;
vector<int>lowHull, upHull, possApples, all;
int ccw (pair<int, int>a, pair<int, int>b, pair<int, int>c) {
return (a.first*(b.second-c.second)+b.first*(c.second-a.second)+c.first*(a.second-b.second));
}
int dist[N][N];
void mHull () {
sort (holes.begin(), holes.end());
for (int i = 0; i < holes.size(); i++) {
while (lowHull.size() > 1 && ccw (holesOG[lowHull[lowHull.size()-2]], holesOG[lowHull[lowHull.size()-1]], holes[i].first) <= 0) {
lowHull.pop_back();
}
lowHull.push_back(holes[i].second);
}
reverse (holes.begin(), holes.end());
for (int i = 0; i < holes.size(); i++) {
while (upHull.size() > 1 && ccw (holesOG[upHull[upHull.size()-2]], holesOG[upHull[upHull.size()-1]], holes[i].first) <= 0) {
upHull.pop_back();
}
upHull.push_back(holes[i].second);
}
}
void checkApples () {
for (int j = 0; j < trees.size(); j++) {
int p1, p2;
int l=0;
for (int i = 0; i < lowHull.size()-1; i++) {
p1 = lowHull[i], p2 = lowHull[i+1];
if (ccw(holesOG[p1], holesOG[p2], trees[j].first) <= 0) {
l=1;
break;
}
}
for (int i = 0; i < upHull.size()-1; i++) {
p1 = upHull[i], p2 = upHull[i+1];
if (ccw(holesOG[p1], holesOG[p2], trees[j].first) <= 0) {
l=1;
break;
}
}
if (!l) possApples.push_back(j);
}
return;
}
bool allIn (int x, int y) {
int br1=0, br2=0;
for (int i = 0; i < possApples.size(); i++) {
if (ccw (holesOG[x], holesOG[y], trees[possApples[i]].first) <= 0) return false;
}
return true;
}
void checkEdges () {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
dist[i][j]=INF;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i!=j && allIn(i, j)) {
dist[i][j]=1;
}
else {
dist[i][j]=INF;
}
}
}
return;
}
int mini;
void floyd () {
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
}
}
}
mini=INF;
for (int i = 0; i < n; i++) {
mini = min(mini, dist[i][i]);
}
return;
}
void solve () {
//cout << ccw (make_pair(800, 300), make_pair(600, 700), make_pair(200, 700));
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> a >> b;
holes.push_back(make_pair(make_pair(a, b), i));
holesOG.push_back(make_pair(a, b));
}
for (int i = 0; i < m; i++) {
cin >> a >> b;
trees.push_back(make_pair(make_pair(a, b), i));
}
mHull ();
checkApples();
checkEdges();
floyd();
if (possApples.empty()) {
cout << trees.size()*111 << endl;
return;
}
cout << mini*20+(trees.size()-possApples.size())*111 << endl;
return;
}
int main () {
solve();
return 0;
}
Compilation message
fence.cpp: In function 'void mHull()':
fence.cpp:23:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for (int i = 0; i < holes.size(); i++) {
| ~~^~~~~~~~~~~~~~
fence.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for (int i = 0; i < holes.size(); i++) {
| ~~^~~~~~~~~~~~~~
fence.cpp: In function 'void checkApples()':
fence.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for (int j = 0; j < trees.size(); j++) {
| ~~^~~~~~~~~~~~~~
fence.cpp:45:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for (int i = 0; i < lowHull.size()-1; i++) {
| ~~^~~~~~~~~~~~~~~~~~
fence.cpp:52:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for (int i = 0; i < upHull.size()-1; i++) {
| ~~^~~~~~~~~~~~~~~~~
fence.cpp: In function 'bool allIn(int, int)':
fence.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for (int i = 0; i < possApples.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~~
fence.cpp:65:9: warning: unused variable 'br1' [-Wunused-variable]
65 | int br1=0, br2=0;
| ^~~
fence.cpp:65:16: warning: unused variable 'br2' [-Wunused-variable]
65 | int br1=0, br2=0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4332 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4332 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
4332 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
4460 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4332 KB |
Output is correct |
