| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1229391 | radodododo | Triangles (CEOI18_tri) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <trilib.h>
using namespace std;
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);
}