제출 #972474

#제출 시각아이디문제언어결과실행 시간메모리
972474Charizard2021Triangles (CEOI18_tri)C++17
0 / 100
1 ms348 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...