#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;
int n;
map < pair < int, int >, bool > bio;
vector < pair < int, int > > v;
deque < pair < int, int > > q;
ll solve(int poc, int kraj){
// cout << poc << " " << kraj << endl;
ll mini=(ll)v[poc].second*v[kraj].first;
int ind=-1;
for(int i=poc; i<kraj; i++){
if((ll)v[poc].second*v[i].first+(ll)v[kraj].first*v[i+1].second<mini){
mini=(ll)v[poc].second*v[i].first+(ll)v[kraj].first*v[i+1].second;
ind=i;
}
}
if(ind==-1){
return mini;
}
return solve(poc, ind)+solve(ind+1, kraj);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
pair < int, int > p;
for(int i=0; i<n; i++){
cin >> p.first >> p.second;
p.first=abs(p.first);
p.second=abs(p.second);
if(!bio[p]){
bio[p]=1;
v.push_back(p);
}
}
n=v.size();
sort(v.begin(), v.end());
for(int i=0; i<n; i++){
while(!q.empty() && q.back().second<=v[i].second){
q.pop_back();
}
q.push_back(v[i]);
}
v.clear();
while(!q.empty()){
v.push_back(q.front());
q.pop_front();
}
n=v.size();
cout << solve(0, n-1)*4 << '\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
8 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
9 |
Incorrect |
7 ms |
640 KB |
Output isn't correct |
10 |
Incorrect |
8 ms |
768 KB |
Output isn't correct |