Submission #1229396

#TimeUsernameProblemLanguageResultExecution timeMemory
1229396radodododoTriangles (CEOI18_tri)C++20
0 / 100
0 ms328 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; #ifdef __cplusplus extern "C" { #endif int get_n(); int is_clockwise(int a, int b, int c); void give_answer(int s); #ifdef __cplusplus } #endif long long ccin_n() { return get_n(); } bool aski(long long a, long long b, long long c) { return is_clockwise(a + 1, b + 1, c + 1); } bool cmpp(long long a, long long b) { if (a == 0) { return true; } if (a == 1) { return a < b; } if (b == 0) { return false; } if (b == 1) { return a < b; } bool aska = aski(1, 0, a); bool askb = aski(1, 0, b); if (aska && !askb) { return true; } if (!aska && askb) { return false; } return aski(a, 0, b); } void say_anse(long long x) { give_answer(x); } int main() { long long n = ccin_n(); vector<long long> srt(n); for (long long i = 0; i < n; i++) { srt[i] = i; } sort(srt.begin(), srt.end(), cmpp); vector<long long> ch; for (auto i : srt) { if (ch.size() < 2) { ch.push_back(i); continue; } while (ch.size() >= 2 && aski(ch[ch.size() - 2], ch.back(), i)) { ch.pop_back(); } ch.push_back(i); } vector<long long> sv = ch; vector<bool> delet(n); for (auto i : srt) { if (ch.size() < 2) { ch.push_back(i); continue; } while (ch.size() >= 2 && aski(ch[ch.size() - 2], ch.back(), i)) { delet[ch.back()] = 1; ch.pop_back(); } ch.push_back(i); } long long ans = sv.size(); for (auto x : sv) { if (delet[x]) { ans--; } } say_anse(ans); }
#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...