Submission #410490

#TimeUsernameProblemLanguageResultExecution timeMemory
410490abdzagTriangles (CEOI18_tri)C++17
0 / 100
1 ms204 KiB
#include<bits/stdc++.h>
#include "trilib.h"
#include<unordered_map>
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
#define rrep(i,a,b) for(int i=int(a);i>int(b);i--)
#define all(v) v.begin(),v.end()
#define trav(a,v) for(auto&a:v)
#define  sz(a) a.size()
typedef long double ld;
using namespace std;
static const long long inf = 1e15;
typedef long long ll;
typedef unsigned long long ull;

int main() {
	ll n;
	n = get_n();
	ll cur = 1;
	ll nxt = 2;
	vector<bool> v(n);
	rep(i, 3, n + 1) {
		if (is_clockwise(cur, nxt, i)) {
			nxt = i;
		}
	}
	v[nxt] = true;
	cur = nxt;
	rep(i, 3, n + 1) {
		while (nxt == cur || v[nxt]) {
			nxt++;
			nxt %= n + 1;
			if (nxt == 0)nxt++;
		}
		rep(i, 1, n + 1) {
			if (i == nxt || i == cur || v[i])continue;
			if (is_clockwise(cur, nxt, i)) {
				nxt = i;
			}
		}
		if (v[nxt])break;
		v[nxt] = 1;
		cur = nxt;
	}
	ll ans = 0;
	rep(i,0,n)ans += v[i];
	give_answer(ans);
	return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...