Submission #54952

#	Time	Username	Problem	Language	Result	Execution time	Memory
54952		linkret	Printed Circuit Board (CEOI12_circuit)	C++14	80 / 100	243 ms	29492 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;

struct line {
	pii a, b;
};

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

vector<line> add[maxn];
vector<line> rem[maxn];
vector<pair<pii, int> > query[maxn];
vector<int> ans;

ll ccw(pii a, pii b, 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(pii(0, 0), a.f, b.f);

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

bool operator==(line x, line y) {
	return x.a == y.a && x.b == y.b;
}

bool operator<(line x, line y) {
	if(x == y)
		return false;

	ll sum = ccw(x.a, y.a, x.b) + ccw(x.b, y.a, y.b);

	if(!sum) {
		if(x.a.s == y.a.s)
			return x.a.f < y.a.f;
		return x.a.f < y.a.f;
	}

	return sum > 0;
}

void sweep() {
	multiset<line> st;

	for(int t = 1; t <= k; t++) {
		for(const line &i : add[t]) {
			st.insert(i);
		}
		
		line f = *st.begin();

		sort(query[t].begin(), query[t].end());

		for(const pair<pii, int> &i : query[t]) {
			if(ccw(f.a, f.b, i.f) == 0) {
				ans.push_back(i.s);
			}

			break;
		}

		for(const line &i : rem[t]) {
			auto it = st.find(i);
			st.erase(it);
		}
	}
}

void add_edge(int i, int j, int x, int y) {
	if(i < j) {
		add[i].push_back(line{org[x], org[y]});
		rem[j].push_back(line{org[x], org[y]});
	} else {
		add[j].push_back(line{org[y], org[x]});
		rem[i].push_back(line{org[y], org[x]});
	}
}

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

	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].push_back(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);
	add_edge(arr[n - 1], arr[0], n - 1, 0);

	sweep();

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

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

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

	cout << endl;

	return 0;
}

• Subtask 1: 80 / 100