| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 121128 | BThero | Triangles (CEOI18_tri) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// Why am I so dumb? :c
// chrono::system_clock::now().time_since_epoch().count()
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include"trilib.h"
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int MAXN = (int)4e4 + 5;
int pivot;
bool cmp(int a, int b) {
return is_clockwise(pivot, a, b);
}
void printVec(vector<int> V) {
printf("Hull is:");
for (int x : V) {
printf(" %d", x);
}
printf("\n");
}
void solve() {
int n = get_n();
int ans = n;
for (pivot = 1; pivot <= n; ++pivot) {
vector<int> idx, V;
for (int j = 1; j <= n; ++j) {
if (j != pivot) {
idx.pb(j);
}
}
sort(all(idx), cmp);
V.pb(pivot);
V.pb(idx[0]);
for (int i = 1; i < idx.size(); ++i) {
while (V.size() >= 2 && !is_clockwise(V[V.size() - 2], V.back(), idx[i])) {
V.pop_back();
}
V.pb(idx[i]);
}
bool good = 1;
for (int i = 0; i < V.size(); ++i) {
good &= is_clockwise(V[i], V[(i + 1) % V.size()], V[(i + 2) % V.size()]);
}
if (good) {
ans = min(ans, V.size());
//printVec(V);
//give_answer(V.size());
//return;
}
}
give_answer(ans);
}
int main() {
int tt = 1;
while (tt--) {
solve();
}
return 0;
}