| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 539093 | aniervs | Triangles (CEOI18_tri) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "trilib.h"
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using db = long double;
const int maxn = 2e5 + 5;
vector<int> arr[2];
void merge_sort(vector<int> &a, int l, int r){
if(l >= r){
return;
}
int mid = (l + r)>>1;
merge_sort(a, l, mid);
merge_sort(a, mid + 1, r);
vector<int> c;
merge(a.begin() + l, a.begin() + mid + 1, a.begin() + mid + 1, a.begin() + r + 1, back_inserter(c), [&a](const int p, const int q){
return !is_clock_wise(a[0], p, q);
});
for(int i = l, j = 0; i <= r; i++, j++){
a[i] = c[j];
}
}
vector<int> compute_convex_hull(vector<int> a){
if(a.size() <= 2)
return a;
merge_sort(a, 1, a.size() - 1);
vector<int> h;
for(auto p:a){
while(h.size() > 1 and is_clock_wise(h[h.size() - 2], h[h.size() - 1], p))
h.pop_back();
h.push_back(p);
}
return h;
}
vector<int> merge_convex(const vector<int> &a, const vector<int> &b){
int n = a.size(), m = b.size();
if(n <= 2) return b;
if(m <= 2) return a;
int l1, l2, r1, r2;
vector<int> c;
{
// upper part
int l = 0, r = 0;
while(true){
if(!is_clock_wise(a[l], b[r], b[(r - 1 + m) % m])) r = (r - 1 + m) % m;
else if(is_clock_wise(b[r], a[l], a[(l + 1)% n])) l = (l + 1) % n;
else break;
}
l1 = l, r1 = r;
}
{
// lower part
int l = 0, r = 0;
while(true){
if(is_clock_wise(a[l], b[r], b[(r + 1) % m])) r = (r + 1) % m;
else if(!is_clock_wise(b[r], a[l], a[(l - 1 + n) % n])) l = (l - 1) % n;
else break;
}
l2 = l, r2 = r;
}
while(true){
c.push_back(a[l1]);
if(l1 == l2) break;
l1 = (l1 + 1) % n;
}
while(true){
c.push_back(b[r2]);
if(r2 == r1) break;
r2 = (r2 + 1) % n;
}
sort(all(c));
c.erase(unique(all(c)), c.end());
return c;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cout.setf(ios::fixed); cout.precision(0);
int n = get_n();
arr[0] = {1}, arr[1] = {2};
for(int i = 3; i <= n; i++){
arr[is_clock_wise(1, 2, i)].push_back(i);
}
arr[0] = compute_convex_hull(arr[0]);
arr[1] = compute_convex_hull(arr[1]);
auto ans = merge_convex(arr[0], arr[1]);
give_answer(ans.size());
return 0;
}