| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 348111 |
2021-01-14T09:37:53 Z |
Harry464 |
Fence (CEOI08_fence) |
C++14 |
|
1 ms |
396 KB |
#include <iostream>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
vector <vector <ll> > adjl(1000);
int main()
{
ll n, m;
cin >> n >> m;
vector <pair<ll,ll> > h(n);
vector <pair<ll,ll> > t(m);
for (int i = 0; i < n; i++)
cin >> h[i].first >> h[i].second;
for (int i = 0; i < m; i++)
cin >> t[i].first >> t[i].second;
vector <ll> uh;
vector <ll> lh;
sort(h.begin(), h.end());
for (int i = 0; i < n; i++){
if (uh.size() < 2){
uh.push_back(i);
continue;
}
ll cx = h[i].first, cy = h[i].second;
ll s = uh.size();
while (s >= 2){
ll bx = h[uh[s-1]].first, by = h[uh[s-1]].second;
ll ax = h[uh[s-2]].first, ay = h[uh[s-2]].second;
ll por = (bx-ax)*(cy-ay) - (cx-ax)*(by-ay);
if (por > 0)
uh.pop_back(), s--;
else
break;
}
uh.push_back(i);
}
for (int i = 0; i < n; i++){
if (lh.size() < 2){
lh.push_back(i);
continue;
}
ll cx = h[i].first, cy = h[i].second;
ll s = lh.size();
while (s >= 2){
ll bx = h[lh[s-1]].first, by = h[lh[s-1]].second;
ll ax = h[lh[s-2]].first, ay = h[lh[s-2]].second;
ll por = (bx-ax)*(cy-ay) - (cx-ax)*(by-ay);
if (por < 0)
lh.pop_back(), s--;
else
break;
}
lh.push_back(i);
}
vector <ll> tacke;
for (int i = 0; i < uh.size(); i++)
tacke.push_back(uh[i]);
for (int i = lh.size() - 2; i >= 1; i--)
tacke.push_back(lh[i]);
vector <ll> odg;
for (int i = 0; i < m; i++){
bool jeste = true;
for (int j = 0; j < uh.size() - 1; j++){
ll bx = h[uh[j+1]].first, by = h[uh[j+1]].second;
ll ax = h[uh[j]].first, ay = h[uh[j]].second;
ll val = (bx-ax)*(t[i].second - ay) - (by - ay)*(t[i].first - ax);
if (val > 0)
jeste = false;
}
for (int j = 0; j < lh.size() - 1; j++){
ll bx = h[lh[j+1]].first, by = h[lh[j+1]].second;
ll ax = h[lh[j]].first, ay = h[lh[j]].second;
ll val = (bx-ax)*(t[i].second - ay) - (by - ay)*(t[i].first - ax);
if (val < 0)
jeste = false;
}
if (jeste)
odg.push_back(i);
}
ll bv = tacke.size();
for (int i = 0; i < bv; i++){
for (int j = 0; j < bv; j++){
if (i == j)
continue;
ll bx = h[tacke[j]].first, by = h[tacke[j]].second;
ll ax = h[tacke[i]].first, ay = h[tacke[i]].second;
bool jed = true;
for (int k = 0; k < odg.size(); k++){
ll val = (bx-ax)*(t[odg[k]].second - ay) - (by - ay)*(t[odg[k]].second - ax);
if (val > 0)
jed = false;
}
if (jed)
adjl[i].push_back(j);
}
}
ll shortest = 10000000;
for (int i = 0; i < bv; i++){
priority_queue <pair<ll, ll>> bfs;
vector <bool> vis(bv,false);
bfs.push(make_pair(0,i));
ll mini = 10000000;
while(bfs.size()){
ll u = bfs.top().second, c = -bfs.top().first;
bfs.pop();
for (int j = 0; j < adjl[u].size(); j++){
ll v = adjl[u][j];
if (v == i){
mini = min(mini,c + 1);
continue;
}
if (!vis[v])
vis[v] = true, bfs.push(make_pair(-(c + 1), v));
}
}
shortest = min(shortest, mini);
}
cout << shortest*20 + (m - odg.size())*111;
}
Compilation message
fence.cpp: In function 'int main()':
fence.cpp:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for (int i = 0; i < uh.size(); i++)
| ~~^~~~~~~~~~~
fence.cpp:72:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for (int j = 0; j < uh.size() - 1; j++){
| ~~^~~~~~~~~~~~~~~
fence.cpp:79:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for (int j = 0; j < lh.size() - 1; j++){
| ~~^~~~~~~~~~~~~~~
fence.cpp:97:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for (int k = 0; k < odg.size(); k++){
| ~~^~~~~~~~~~~~
fence.cpp:115:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for (int j = 0; j < adjl[u].size(); j++){
| ~~^~~~~~~~~~~~~~~~
| # |
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 |
396 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 |
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 |
- |
