# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
791965 | ttamx | Triangles (CEOI18_tri) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include"trilib.c"
#include<bits/stdc++.h>
using namespace std;
vector<int> lower,upper;
deque<int> hull;
set<int> ans;
bool cmp(int x,int y){
return is_clockwise(1,x,y);
}
void upd(int x){
while(hull.size()>1&&!is_clockwise(hull.end()[-2],hull.back(),x))hull.pop_back();
hull.emplace_back(x);
}
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
int n;
n=get_n();
for(int i=3;i<=n;i++){
if(is_clockwise(1,2,i))upper.emplace_back(i);
else lower.emplace_back(i);
}
sort(lower.begin(),lower.end(),cmp);
sort(upper.begin(),upper.end(),cmp);
for(int i=0;i<2;i++){
upd(1);
for(auto x:lower)upd(x);
upd(2);
for(auto x:upper)upd(x);
}
for(auto x:hull)ans.emplace(x);
give_answer(ans.size());
}