# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
792119 | PoonYaPat | Triangles (CEOI18_tri) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> up,down;
deque<int> dq;
bool comp(int a, int b) {return is_clockwise(1,a,b);}
void add(int x) {
while (dq.size()>=2 && !is_clockwise(dq[dq.size()-2],dq[dq.size()-1],x)) dq.pop_back();
dq.push_back(x);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
n=get_n();
for (int i=3; i<=n; ++i) {
if (is_clockwise(1,2,i)) down.push_back(i);
else up.push_back(i);
}
sort(up.begin(),up.end(),comp);
sort(down.begin(),down.end(),comp);
add(1);
for (auto s : up) add(s);
add(2);
for (auto s : down) add(s);
int cnt=dq.size();
while (cnt--) {
add(dq.front());
dq.pop_front();
}
give_answer(dq.size());
}