oj.uz

Submission #54946

# Submission time Handle Problem Language Result Execution time Memory
54946 2018-07-05T14:07:32 Z linkret Printed Circuit Board (CEOI12_circuit) C++14
75 / 100
 100 ms 29524 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;

	// if(x.a == y.a)
	// 	return x.b < y.b;

	// if(x.a == y.b)
	// 	return x.b < y.a;

	// if(x.b == y.a)
	// 	return x.a < y.b;

	// if(x.b == y.b)
	// 	return x.a < y.a;

	bool ret = false;
	
	ll sum = ccw(pii(0, 0), y.a, y.b)
		+ ccw(pii(0, 0), y.b, x.b)
	 	+ ccw(pii(0, 0), x.b, x.a)
		+ ccw(pii(0, 0), x.a, y.a);

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

	ret = sum > 0;
	
	// ll xa, xb, ya, yb;
	// xa = ccw(x.a, x.b, y.a);
	// xb = ccw(x.a, x.b, y.b);
	// ya = ccw(y.a, y.b, x.a);
	// yb = ccw(y.a, y.b, x.b);

	// if(!xa && !xb && !ya && !yb) {
	// 	if(x.a.s == y.a.s)
	// 		return x.a.f < y.a.f;
	// 	return x.a.f < y.a.f;
	// }

	// // cout << "values: " << xa << " " << xb << " " << ya << " " << yb << endl;

	// if((xa > 0) == (xb > 0) || !xa || !xb) {
	// 	if(!xa)
	// 		ret = xb < 0;
	// 	else
	// 		ret = xa < 0;
	// } else if ((ya > 0) == (yb > 0) || !ya || !yb) {
	// 	if(!ya)
	// 		ret = yb > 0;
	// 	else
	// 		ret = ya > 0;
	// } else {
	// 	// cout << x.a.f << "," << x.a.s << "-" << x.b.f << "," << x.b.s << " " << y.a.f << "," << y.a.s << "-" << y.b.f << "," << y.b.s << endl;
	// 	assert(false);
	// }
	
	// cout << ret << "  " << ": " << x.a.f << "," << x.a.s << "-" << x.b.f << "," << x.b.s << " " << y.a.f << "," << y.a.s << "-" << y.b.f << "," << y.b.s << endl;
	// cout << endl;

	return ret;
}

void sweep() {
	multiset<line> st;

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

		// if(t == 102) {
		// 	for(auto i : st)
		// 	cout << i.a.f << "," << i.a.s << "-" << i.b.f << "," << i.b.s << " ";
		// 	cout << endl;
		// }

		// assert(!st.empty());
		
		line f = *st.begin();

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

		for(const pair<pii, int> &i : query[t]) {
			// assert(!st.empty());

			if(ccw(f.a, f.b, i.f) == 0) {
				ans.push_back(i.s);
			}

			break;
		}

		// cout << "trebam izbrisat: ";

		// for(const line &i : rem[t]) {
		// 	cout << i.a.f << "," << i.a.s << "-" << i.b.f << "," << i.b.s << " ";
		// }
		// cout << endl;

		for(const line &i : rem[t]) {
			// cout<<(i < i)<<endl;
			auto it = st.find(i);
			// assert(it != st.end());
			// if(it != st.end())
				st.erase(it);
		}

		// cout << "success ";

		// cout << t << ": ";

		// for(line i : st) {
		// 	cout << i.a.f << "," << i.a.s << "-" << i.b.f << "," << i.b.s << " ";
		// }
		// cout << endl;
	}
}

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);

	// while(true) {
	// 	int a, b, c, d;
	// 	cin >> a >> b >> c >> d;
	// 	line x{pii(a, b), pii(c, d)};
	
	// 	int aa, bb, cc, dd;
	// 	cin >> aa >> bb >> cc >> dd;
	// 	line y{pii(aa, bb), pii(cc, dd)};
		
	// 	cout << (x < y) << endl;
	// }

	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; i++) {
	// 	cout << arr[i] << " ";
	// }

	// cout << endl;

	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);

	// for(int i = 1; i <= n; i++) {
	// 	cout << i << ": ";
		
	// 	for(line j : add[i]) {
	// 		cout << j.a.f << "," << j.a.s << "-" << j.b.f << "," << j.b.s << " ";
	// 	}
	// 	cout << endl;
	// }
	// cout << endl;

	// cout << arr[21] << " " << arr[22] << endl;

	sweep();

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

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

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

	cout << endl;

	return 0;
}

Subtask #1
75.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9592 KB Output is correct
2 Correct 11 ms 9832 KB Output is correct
3 Correct 14 ms 10016 KB Output is correct
4 Correct 16 ms 10192 KB Output is correct
5 Correct 33 ms 10900 KB Output is correct
6 Correct 23 ms 10900 KB Output is correct
7 Correct 41 ms 12272 KB Output is correct
8 Correct 20 ms 12272 KB Output is correct
9 Correct 19 ms 12272 KB Output is correct
10 Correct 24 ms 12272 KB Output is correct
11 Correct 23 ms 12272 KB Output is correct
12 Correct 27 ms 12272 KB Output is correct
13 Correct 56 ms 13400 KB Output is correct
14 Correct 55 ms 14168 KB Output is correct
15 Correct 59 ms 15392 KB Output is correct
16 Execution timed out 110 ms 20868 KB Time limit exceeded
17 Execution timed out 194 ms 22020 KB Time limit exceeded
18 Runtime error 66 ms 27260 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 77 ms 29524 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 69 ms 29524 KB Execution killed with signal 11 (could be triggered by violating memory limits)