Submission #973812

#TimeUsernameProblemLanguageResultExecution timeMemory
973812efedmrlrTriangles (CEOI18_tri)C++17
0 / 100
1 ms344 KiB
#include <bits/stdc++.h> #include "trilib.h" #define lli long long int #define ld long double #define pb push_back #define MP make_pair #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define REP(i, n) for(int i = 0; (i) < (n); (i)++) using namespace std; void fastio() { ios_base::sync_with_stdio(false); cin.tie(NULL); } int n; void find_hull(vector<int> &p, vector<int> &hull) { if(p.size() < 3) return; int piv = p[0]; p.erase(p.begin()); auto comp = [&piv](int x, int y) { return is_clockwise(piv, x, y); }; sort(all(p), comp); hull.clear(); hull.pb(piv); hull.pb(p[0]); for(int i = 2; i < p.size(); i++) { while(hull.size() > 1 && !is_clockwise(hull[hull.size() - 2], hull.back(), p[i])) { hull.pop_back(); } hull.pb(p[i]); } } void solve() { n = get_n(); vector<int> p; for(int i = 1; i <= n; i++) { p.pb(i); } vector<int> pl = {2, 1}, pr = {1, 2}; for(int i = 3; i <= n; i++) { if(is_clockwise(1, 2, i)) { pl.pb(i); } else { pr.pb(i); } } vector<int> hull1, hull2; find_hull(pl, hull1); find_hull(pr, hull2); // hull1 starts with 2, hull2 starts with 1 // cout << "hull1: "; // for(auto c : hull1) { // cout << c << " "; // } // cout << "\nhull2: "; // for(auto c : hull2) { // cout << c << " "; // } // cout << "\n"; hull1.pop_back(); hull2.pop_back(); reverse(all(hull1)); while(1) { if(hull1.size() > 1 && hull2.size() && !is_clockwise(hull2.back(), hull1.back(), hull1[hull1.size() - 2])) { hull1.pop_back(); continue; } if(hull2.size() > 1 && hull1.size() && !is_clockwise(hull2[hull2.size() - 2], hull2.back(), hull1.back())) { hull2.pop_back(); continue; } break; } reverse(all(hull1)); reverse(all(hull2)); while(1) { if(hull1.size() > 1 && hull2.size() && is_clockwise(hull2.back(), hull1.back(), hull1[hull1.size() - 2])) { hull1.pop_back(); continue; } if(hull2.size() > 1 && hull1.size() && is_clockwise(hull2[hull2.size() - 2], hull2.back(), hull1.back())) { hull2.pop_back(); continue; } break; } for(auto c : hull2) { hull1.pb(c); } sort(all(hull1)); hull1.resize(unique(all(hull1)) - hull1.begin()); give_answer(hull1.size()); } signed main() { solve(); }

Compilation message (stderr)

tri.cpp: In function 'void find_hull(std::vector<int>&, std::vector<int>&)':
tri.cpp:30:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i = 2; i < p.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...