Submission #72756

#	Time	Username	Problem	Language	Result	Execution time	Memory
72756		chpipis	Triangles (CEOI18_tri)	C++11	100 / 100	748 ms	58104 KiB

tri

#include "trilib.h"
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()

typedef vector<int> vi;

const int MAXN = 4e4 + 5;

int q_cnt;
map<int, map<int, bool> > memo[MAXN];

bool ccw(int a, int b, int c) {
	q_cnt++;
	if (q_cnt > (int)1e6) {
		give_answer(40000);
		exit(0);
	}
	//assert(q_cnt <= (int)1e6);
	if (a == b || b == c || a == c) {
		assert(false);
		//while (true) {}
	}

	if (memo[a].count(b) && memo[a][b].count(c))
		return memo[a][b][c];
	//else if (memo[a][c].count(b))
	//	return !memo[a][c][b];
	else if (memo[b].count(c) && memo[b][c].count(a))
		return memo[b][c][a];
	//else if (memo[c][a].count(b))
	//	return memo[c][a][b];
	return memo[a][b][c] = !is_clockwise(a, b, c);
}

struct comp {
	int k;
	comp(int _k) : k(_k) {}
	bool operator ()(const int &lhs, const int &rhs) const {
		if (lhs == k) return true;
		if (rhs == k) return false;
		return ccw(k, lhs, rhs);
	}
};

vi convex_hull(vi pts) {
	int n = (int)pts.size();
	/// SUPER SOS: SORT THE POINTS BEFORE RETURNING THEM
	/// THEY MUST BE IN CCW ORDER
	sort(all(pts), comp(pts[0]));
	if (n <= 3) {
		/*
		printf("convex hull:");
		for (auto it : pts) printf(" %d", it);
		puts("");
		*/
		return pts;
	}
	vi hull;
	int sz = 0;
	for (int i = 0; i < n; i++) {
		while (sz >= 2 && ccw(hull[sz - 2], pts[i], hull[sz - 1])) {
			hull.pop_back();
			sz--;
		}
		hull.pb(pts[i]);
		sz++;
	}
	/*
	printf("convex hull:");
	for (auto it : hull) printf(" %d", it);
	puts("");
	*/
	return hull;
}

#define inc(i, n) ((i + 1) % n)
#define dec(i, n) ((i + n - 1) % n)

int main() {
	q_cnt = 0;
	int n = get_n();
	if (n <= 3) {
		give_answer(n);
		return 0;
	}
	vi one, two;
	one = {1, 2};
	int who = -1;
	for (int i = 3; i <= n; i++) {
		if (ccw(1, 2, i))
			one.pb(i);
		else {
			if (who == -1)
				who = i;
			else if (ccw(1, i, who))
				who = i;
			two.pb(i);
		}
	}
	one = convex_hull(one);
	if (two.size() > 1) {
		swap(two[0], two[find(all(two), who) - two.begin()]);
	}
	two = convex_hull(two);
	int os = (int)one.size(), ts = (int)two.size();
	if (ts == 0) {
		give_answer(os);
		return 0;
	}
	// find ccw tangent
	int j = 0;
	pair<int, int> le(-1, -1), ri(-1, -1);
	for (int i = 0; i < os; i++) {
		if (ts > 1) {
			while (!ccw(one[i], two[j], two[dec(j, ts)]) ||
			!ccw(one[i], two[j], two[inc(j, ts)]))
				j = inc(j, ts);
		}
		if (ccw(two[j], one[dec(i, os)], one[i]) && ccw(two[j], one[inc(i, os)], one[i])) {
			ri = mp(i, j);
			break;
		}
	}
	j = 0;
	for (int i = 0; i < os; i++) {
		if (ts > 1) {
			while (ccw(one[i], two[j], two[dec(j, ts)]) ||
			ccw(one[i], two[j], two[inc(j, ts)]))
				j = dec(j, ts);
		}
		if (!ccw(two[j], one[dec(i, os)], one[i]) && !ccw(two[j], one[inc(i, os)], one[i])) {
			le = mp(i, j);
			break;
		}
	}
	//printf("le: (%d, %d), ri: (%d, %d)\n", le.fi, le.se, ri.fi, ri.se);
	int ans = 2;
	for (int i = ri.se; i != le.se; i = inc(i, ts))
		ans++;
	for (int i = le.fi; i != ri.fi; i = inc(i, os))
		ans++;
	give_answer(ans);
	//give_answer((ri.se - le.se + ts) % ts + (le.fi - ri.fi + os) % os);
	return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 25 / 25