#include<bits/stdc++.h>
#define breturn return
using namespace std;
vector<pair<int, int> > kor, hull, bruh;
pair<int, int> poc;
int n, a, b, c, dp[5002];
bool ccw(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
// cout << a.first << " " << a.second << " - " << b.first << " " << b.second << " - " << c.first << " " << c.second << '\n';
if(a.first * (b.second - c.second) + b.first * (c.second - a.second) + c.first * (a.second - b.second) < 0) breturn true;
else breturn false;
}
int main() {
cin >> n;
c = -1;
for(int i = 0; i < n; i++) {
cin >> a >>b;
a = abs(a), b = abs(b);
kor.push_back({a, b});
if(b > c) c = b, poc = {a, b};
}
if(n == 1) breturn cout << a * b << '\n', 0;
sort(kor.begin(), kor.end());
int x = 0;
while(kor[x] != poc) x++;
hull.push_back(kor[x]);
for(int i = x; i < n; i++) {
if(kor[i].first > hull[hull.size() - 1].first and kor[i].second < hull[hull.size() - 1].second) hull.push_back(kor[i]);
}
dp[0] = 0;
for(int i = 0; i < hull.size(); i++) {
bruh.push_back({hull[i].second, dp[i]});
int l = 0;
int r = bruh.size() - 1;
while(l != r) {
int mid = (l + r)/2;
if(bruh[mid].first * hull[i].first + bruh[mid].second > bruh[mid + 1].first * hull[i].first + bruh[mid + 1].second) l = mid + 1;
else r = mid;
}
dp[i + 1] = bruh[l].first * hull[i].first + bruh[l].second;
}
cout << dp[hull.size()] * 4;
}
Compilation message
cover.cpp: In function 'int main()':
cover.cpp:30: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]
30 | for(int i = 0; i < hull.size(); i++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 6 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 7 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 8 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 9 |
Incorrect |
3 ms |
364 KB |
Output isn't correct |
| 10 |
Incorrect |
5 ms |
492 KB |
Output isn't correct |
