#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);
long long ii = -1;
for (long long i = 1; i + 1 < n; i++) {
if (aski(0, i, i + 1)) {
ii = i + 1;
}
}
if (ii == -1) {
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);
}
else {
vector<long long> newsrt = { 0 };
for (long long j = ii; j < n; j++) {
newsrt.push_back(srt[j]);
}
for (long long j = 1; j < ii; j++) {
newsrt.push_back(srt[j]);
}
srt = newsrt;
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);
}
say_anse(ch.size());
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |