제출 #246950

#제출 시각아이디문제언어결과실행 시간메모리
246950tonowakTriangles (CEOI18_tri)C++17
20 / 100
5 ms432 KiB
#include <bits/stdc++.h> // Tomasz Nowak #include "trilib.h" using namespace std; // XIII LO Szczecin using LL = long long; // Poland #define FOR(i, l, r) for(int i = (l); i <= (r); ++i) #define REP(i, n) FOR(i, 0, (n) - 1) template<class T> int size(T &&x) { return int(x.size()); } template<class A, class B> ostream& operator<<(ostream &out, const pair<A, B> &p) { return out << '(' << p.first << ", " << p.second << ')'; } template<class T> auto operator<<(ostream &out, T &&x) -> decltype(x.begin(), out) { out << '{'; for(auto it = x.begin(); it != x.end(); ++it) out << *it << (it == prev(x.end()) ? "" : ", "); return out << '}'; } void dump() {} template<class T, class... Args> void dump(T &&x, Args... args) { cerr << x << "; "; dump(args...); } #ifdef DEBUG struct Nl{~Nl(){cerr << '\n';}}; # define debug(x...) cerr << (strcmp(#x, "") ? #x ": " : ""), dump(x), Nl(), cerr << "" #else # define debug(...) 0 && cerr #endif mt19937_64 rng(0); int rd(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); } // end of templates bool dir_right(int a, int b, int c) { return is_clockwise(a + 1, b + 1, c + 1); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n = get_n(); debug(n); array<vector<int>, 2> halfplane; FOR(i, 2, n - 1) halfplane[dir_right(0, 1, i)].emplace_back(i); debug(halfplane); array<vector<int>, 2> halfhull; REP(iter, 2) { halfplane[iter].emplace_back(1); sort(halfplane[iter].begin(), halfplane[iter].end(), [&](int a, int b) { if(a == b) return false; return dir_right(0, a, b) != iter; }); halfplane[iter].emplace(halfplane[iter].begin(), 0); debug(halfplane[iter]); auto &hp = halfplane[iter], &hh = halfhull[iter]; for(int p : hp) { while(size(hh) >= 2 and dir_right(hh.end()[-2], hh.back(), p) == iter) hh.pop_back(); hh.emplace_back(p); } debug(iter, hh); if(iter) hh.erase(prev(hh.end())); else hh.erase(hh.begin()); debug(iter, hh); } REP(iter, 2) { for(auto &hh : halfhull) reverse(hh.begin(), hh.end()); debug(halfhull); while(size(halfhull[0]) >= 2 and size(halfhull[1]) >= 1 and dir_right(halfhull[0].end()[-2], halfhull[0].back(), halfhull[1].back()) != iter) halfhull[0].pop_back(); while(size(halfhull[0]) >= 1 and size(halfhull[1]) >= 2 and dir_right(halfhull[0].back(), halfhull[1].back(), halfhull[1].end()[-2]) != iter) halfhull[1].pop_back(); } debug(halfhull); give_answer(size(halfhull[0]) + size(halfhull[1])); }
#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...