# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
873364 | Darren0724 | Triangles (CEOI18_tri) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "trilib.h"
#ifndef ONLINE_JUDGE
#include "trilib.c"
#endif
using namespace std;
int32_t main() {
int n=get_n();
//int cnt=0;
//int ans=0;
//int i=1;
vector<int> r[2];
//vector<int> ans[2];
vector<int> s[2];
for(int j=3;j<=n;j++){
int t=is_clockwise(1,2,j);
r[t].push_back(j);
}
for(int y=0;y<2;y++){
sort(r[y].begin(),r[y].end(),[&](int a,int b){return is_clockwise(1,b,a);});
s[y].push_back(y==0?2:1);
for(int i:r[y]){
while(s[y].size()>1&&is_clockwise(s[y].end()[-2],s[y].end()[-1],i)){
s[y].pop_back();
}
s[y].push_back(i);
}
}
for(int i:s[1]){
while(s[0].size()>1&&is_clockwise(s[0].end()[-2],s[0].end()[-1],i)){
s[0].pop_back();
}
s[0].push_back(i);
}
give_answer(s[0].size());
return 0;
}