Submission #54990

#	Time	Username	Problem	Language	Result	Execution time	Memory
54990		linkret	Printed Circuit Board (CEOI12_circuit)	C++14	75 / 100	346 ms	33792 KiB

circuit

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define f first
#define s second

const int maxn = 1 << 17, inf = 1e9;

struct line {
	int a, b;
};

int n, k;
pair<pii, int> p[maxn];
pii org[maxn];
int arr[maxn];

int addlen[maxn], remlen[maxn];

line *add[maxn];
line *rem[maxn];

pair<pii, int> query[maxn];

vector<int> ans;

pii zero;

ll ccw(const pii &a, const pii &b, const pii &c) {
	return ll(a.f) * (b.s - c.s) + ll(b.f) * (c.s - a.s) + ll(c.f) * (a.s - b.s);
}

bool comp(pair<pii, int> a, pair<pii, int> b) {
	ll c = ccw(zero, a.f, b.f);

	if(c == 0)
		return a.s < b.s;
	return c > 0;
}

bool operator<(line x, line y) {
	const pii &xa = org[x.a];
	const pii &xb = org[x.b];

	const pii &ya = org[y.a];
	const pii &yb = org[y.b];

	if(xa == ya && xb == yb)
		return false;

	ll sum = ccw(xa, ya, xb) + ccw(xb, ya, yb);

	if(!sum) {
		if(xa.s == ya.s)
			return xa.f < ya.f;
		return xa.f < ya.f;
	}

	return sum > 0;
}

void sweep() {
	multiset<line> st;

	for(int t = 1; t <= k; t++) {
		for(int i = 0; i < addlen[t]; i++) {
			st.insert(add[t][i]);
		}
		
		if(!st.empty()) {
			line f = *st.begin();

			auto mnm = query[t];
			
			if(ccw(org[f.a], org[f.b], mnm.f) == 0) {
				ans.push_back(mnm.s);
			}
		}

		for(int i = 0; i < remlen[t]; i++) {
			auto it = st.find(rem[t][i]);
			st.erase(it);
		}
	}
}

void add_edge(int i, int j, int x, int y, bool b) {
	if(i < j) {
		if(b) {
			addlen[i]++;
			remlen[j]++;
		} else {
			add[i][addlen[i]++] = line{x, y};
			rem[j][remlen[j]++] = line{x, y};
		}
	} else {
		if(b) {
			addlen[j]++;
			remlen[i]++;
		} else {
			add[j][addlen[j]++] = line{y, x};
			rem[i][remlen[i]++] = line{y, x};
		}
	}
}

void compress() {
	sort(p, p + n, comp);

	for(int i = 0; i <= n; i++) {
		query[i] = {{inf, inf}, inf};
	}

	for(int i = 0; i < n; i++) {
		if(i == 0 || ccw(pii(0, 0), p[i].f, p[i - 1].f))
			k++;
		arr[p[i].s] = k;
		query[k] = min(query[k], p[i]);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n;

	for(int i = 0; i < n; i++) {
		pii tmp;
		cin >> tmp.f >> tmp.s;
		
		p[i].f = tmp;
		p[i].s = i;

		org[i] = p[i].f;
	}

	compress();

	for(int i = 0; i < n - 1; i++) 
		add_edge(arr[i], arr[i + 1], i, i + 1, true);
	add_edge(arr[n - 1], arr[0], n - 1, 0, true);

	for(int i = 1; i <= k; i++) {
		add[i] = new line[addlen[i]];
		rem[i] = new line[remlen[i]];
		
		addlen[i] = 0;
		remlen[i] = 0;
	}

	for(int i = 0; i < n - 1; i++) 
		add_edge(arr[i], arr[i + 1], i, i + 1, false);
	add_edge(arr[n - 1], arr[0], n - 1, 0, false);

	sweep();

	cout << ans.size() << endl;

	sort(ans.begin(), ans.end());

	for(int i : ans) {
		cout << i + 1 << " ";
	}

	cout << endl;

	return 0;
}

• Subtask 1: 75 / 100