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"
using namespace std;
vector<int> orderDivide(vector<int> points){
if((int)points.size() <= 1){
return points;
}
int cur = points[rand() % (int)points.size()];
vector<int> leftHalf;
vector<int> rightHalf;
for(int i = 0; i < (int)points.size(); i++){
if(points[i] != cur){
if(is_clockwise(1, cur, points[i])){
rightHalf.push_back(points[i]);
}
else{
leftHalf.push_back(points[i]);
}
}
}
vector<int> leftorderDivide = orderDivide(leftHalf);
vector<int> rightorderDivide = orderDivide(rightHalf);
leftorderDivide.push_back(cur);
for(int a : rightorderDivide){
leftorderDivide.push_back(a);
}
return leftorderDivide;
}
int main(){
srand((unsigned) time(NULL));
int n = get_n();
vector<int> points;
for(int i = 2; i <= n; i++){
points.push_back(i);
}
points = orderDivide(points);
points.insert(points.begin(), 1);
vector<int> cur;
cur.push_back(1);
for(int i = 1; i < (int)points.size(); i++){
while((int)cur.size() >= 2 && !is_clockwise(cur[(int)cur.size() - 2], cur.back(), points[i])){
cur.pop_back();
}
cur.push_back(points[i]);
}
deque<int> dq;
for(int i = 0; i < (int)points.size(); i++){
dq.push_back(points[i]);
}
while(true){
bool works = true;
int cur = dq.back();
dq.pop_back();
if(is_clockwise(dq.back(), cur, dq.front())){
dq.push_back(cur);
}
else{
works = false;
}
cur = dq.front();
dq.pop_front();
if(is_clockwise(dq.back(), cur, dq.front())){
dq.push_front(cur);
}
else{
works = false;
}
if(works){
break;
}
}
give_answer(dq.size());
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |