Submission #1266116

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266116		kaiboy	Printed Circuit Board (CEOI12_circuit)	C++20	100 / 100	70 ms	3656 KiB

circuit

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 200000;

int xx[N], yy[N], ii[N], n;
int pq[N], iq[N + 1], pq_cnt;

long long cross(int x0, int y0, int x1, int y1) {
	return (long long) x0 * y1 - (long long) x1 * y0;
}

long long cross(int i, int j) {
	return cross(xx[i], yy[i], xx[j], yy[j]);
}

long long cross(int i, int j, int k) {
	int xi = xx[i], yi = yy[i];
	int xj = xx[j], yj = yy[j];
	int xk = xx[k], yk = yy[k];
	return cross(xj - xi, yj - yi, xk - xi, yk - yi);
}

bool lt(int i, int j) {
	int i_ = (i + 1) % n, j_ = (j + 1) % n;
	if (cross(i, i_) < 0)
		swap(i, i_);
	if (cross(j, j_) < 0)
		swap(j, j_);
	return (cross(i, i_, j) < 0) + (cross(i, i_, j_) < 0) > (cross(j, j_, i) < 0) + (cross(j, j_, i_) < 0);
}

int p2(int p) {
	return (p <<= 1) > pq_cnt ? 0 : p ^ (p < pq_cnt && lt(iq[p ^ 1], iq[p]));
}

void pq_up(int i) {
	int j, p, q;
	for (p = pq[i]; (q = p >> 1) && lt(i, j = iq[q]); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_dn(int i) {
	int j, p, q;
	for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_add(int i) {
	pq[i] = ++pq_cnt, pq_up(i);
}

void pq_remove(int i) {
	int j = iq[pq_cnt--];
	if (i != j)
		pq[j] = pq[i], pq_up(j), pq_dn(j);
	pq[i] = 0;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> xx[i] >> yy[i], ii[i] = i;
	sort(ii, ii + n, [] (int i, int j) {
			long long c = cross(i, j);
			return c ? c > 0 : xx[i] < xx[j];
			});
	int m = 0;
	for (int h = 0, h_ = 0; h < n; ) {
		int i_ = ii[h];
		for (int i; h_ < n && !cross(i_, i = ii[h_]); h_++) {
			int j = (i - 1 + n) % n;
			if (cross(i, j) < 0)
				pq_remove(j);
			j = (i + 1) % n;
			if (cross(i, j) < 0)
				pq_remove(i);
		}
		bool yes = true;
		if (pq_cnt) {
			int i = iq[1], j = (i + 1) % n;
			if (cross(i, j) < 0)
				swap(i, j);
			if (cross(i, j, ii[h]) < 0)
				yes = false;
		}
		if (yes)
			ii[m++] = i_;
		while (h < h_) {
			int i = ii[h++], j = (i - 1 + n) % n;
			if (cross(i, j) > 0)
				pq_add(j);
			j = (i + 1) % n;
			if (cross(i, j) > 0)
				pq_add(i);
		}
	}
	sort(ii, ii + m);
	cout << m << '\n';
	for (int h = 0; h < m; h++)
		cout << ii[h] + 1 << ' ';
	cout << '\n';
	return 0;
}

• Subtask 1: 100 / 100