oj.uz

Submission #54952

# Submission time Handle Problem Language Result Execution time Memory
54952 2018-07-05T14:19:08 Z linkret Printed Circuit Board (CEOI12_circuit) C++14
80 / 100
 100 ms 29492 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9592 KB Output is correct
2 Correct 12 ms 9832 KB Output is correct
3 Correct 16 ms 10036 KB Output is correct
4 Correct 12 ms 10212 KB Output is correct
5 Correct 21 ms 10904 KB Output is correct
6 Correct 20 ms 10912 KB Output is correct
7 Correct 35 ms 12188 KB Output is correct
8 Correct 18 ms 12188 KB Output is correct
9 Correct 18 ms 12188 KB Output is correct
10 Correct 21 ms 12188 KB Output is correct
11 Correct 25 ms 12188 KB Output is correct
12 Correct 26 ms 12188 KB Output is correct
13 Correct 51 ms 13424 KB Output is correct
14 Correct 66 ms 14136 KB Output is correct
15 Correct 53 ms 15336 KB Output is correct
16 Correct 99 ms 20852 KB Output is correct
17 Execution timed out 243 ms 21916 KB Time limit exceeded
18 Runtime error 63 ms 27124 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 67 ms 29492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 62 ms 29492 KB Execution killed with signal 11 (could be triggered by violating memory limits)