| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 503647 | andrei_boaca | Triangles (CEOI18_tri) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "trilib.h"
#include "trilib.c"
using namespace std;
mt19937 rng(time(NULL));
map<vector<int>,bool> f;
set<int> border;
vector<int> stiva,q;
int root;
int calls;
bool isgood(int a,int b,int c)
{
vector<int> v;
v.push_back(a);
v.push_back(b);
v.push_back(c);
sort(v.begin(),v.end());
if(f.count(v)==0)
{
f[v]=is_clockwise(v[0],v[1],v[2]);
calls++;
assert(calls<=1e6);
}
bool ans=f[v];
int nr=0;
if(a!=v[0])
nr++;
if(b!=v[1])
nr++;
if(c!=v[2])
nr++;
if(nr%2==0&&nr>0)
ans=!ans;
return ans;
}
bool comp(int a, int b)
{
if(is_clockwise(root,a,b))
return 1;
return 0;
}
int main()
{
int n;
n=get_n();
int start=1;
int j=0;
if(start==2)
j=1;
else
j=2;
for(int i=1;i<=n;i++)
if(start!=i&&j!=i)
if(!is_clockwise(start,j,i))
j=i;
stiva.push_back(j);
root=j;
for(int i=1;i<=n;i++)
if(i!=root)
q.push_back(i);
sort(q.begin(),q.end(),comp);
stiva.push_back(q[0]);
for(int i=1;i<q.size();i++)
{
int nod=q[i];
while(stiva.size()>2)
{
int lg=stiva.size();
int b=stiva[lg-1];
int a=stiva[lg-2];
if(!is_clockwise(a,b,nod))
stiva.pop_back();
else
break;
}
stiva.push_back(nod);
}
give_answer(stiva.size());
for(auto i:stiva)
cout<<i<<' ';
return 0;
}