제출 #74440

#제출 시각아이디문제언어결과실행 시간메모리
74440szawinisTriangles (CEOI18_tri)C++17
75 / 100
49 ms24560 KiB
#include <bits/stdc++.h> #include "trilib.h" #define long long long using namespace std; int n; vector<int> up, down, up_hull, down_hull, ans; int main() { 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); } up.push_back(2); down.push_back(2); sort(up.begin(), up.end(), [] (int j, int k) { return is_clockwise(1, j, k); }); sort(down.begin(), down.end(), [] (int j, int k) { return !is_clockwise(1, j, k); }); if(up.size() > 1) { up_hull.push_back(1); up_hull.push_back(up[0]); for(int i = 1; i < up.size(); i++) { while(up_hull.size() >= 2 && !is_clockwise(up_hull[up_hull.size()-2], up_hull[up_hull.size()-1], up[i])) up_hull.pop_back(); up_hull.push_back(up[i]); } } if(down.size() > 1) { down_hull.push_back(1); down_hull.push_back(down[0]); for(int i = 1; i < down.size(); i++) { while(down_hull.size() >= 2 && is_clockwise(down_hull[down_hull.size()-2], down_hull[down_hull.size()-1], down[i])) down_hull.pop_back(); down_hull.push_back(down[i]); } } if(!down_hull.empty() && !up_hull.empty()) { if(down_hull[0] == 1 && up_hull[0] == 1) down_hull.erase(down_hull.begin()); if(down_hull.back() == 2 && up_hull.back() == 2) down_hull.pop_back(); } reverse(down_hull.begin(), down_hull.end()); vector<int> res = up_hull; for(int i: down_hull) res.push_back(i); vector<int> ans; ans.push_back(res[0]); ans.push_back(res[1]); for(int i = 2; i < res.size(); i++) { while(ans.size() >= 2 && !is_clockwise(ans[ans.size()-2], ans[ans.size()-1], res[i])) ans.pop_back(); ans.push_back(res[i]); } deque<int> ans_dq; for(int i: ans) ans_dq.push_back(i); while(ans.size() >= 3) { bool found = false; int x = ans_dq.front(); ans_dq.pop_front(); if(is_clockwise(ans_dq.back(), x, ans_dq.front())) ans_dq.push_front(x); else found = true; x = ans_dq.back(); ans_dq.pop_back(); if(is_clockwise(ans_dq.back(), x, ans_dq.front())) ans_dq.push_back(x); else found = true; if(!found) break; } /* for(int i: up) cout << i << ' '; */ /* cout << endl; */ /* for(int i: down) cout << i << ' '; */ /* cout << endl; */ /* for(int i: up_hull) cout << i << ' '; */ /* cout << endl; */ /* for(int i: down_hull) cout << i << ' '; */ /* cout << endl; */ /* for(int i: ans_dq) cout << i << ' '; */ /* cout << endl; */ give_answer(ans_dq.size()); }

컴파일 시 표준 에러 (stderr) 메시지

tri.cpp: In function 'int main()':
tri.cpp:21:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < up.size(); i++) {
                  ~~^~~~~~~~~~~
tri.cpp:30:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < down.size(); i++) {
                  ~~^~~~~~~~~~~~~
tri.cpp:47:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 2; i < res.size(); i++) {
                 ~~^~~~~~~~~~~~
#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...