oj.uz

Submission #54944

# Submission time Handle Problem Language Result Execution time Memory
54944 2018-07-05T14:04:13 Z linkret Printed Circuit Board (CEOI12_circuit) C++14
75 / 100
 100 ms 29676 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 9 ms 9592 KB Output is correct
2 Correct 10 ms 9828 KB Output is correct
3 Correct 12 ms 10216 KB Output is correct
4 Correct 13 ms 10216 KB Output is correct
5 Correct 23 ms 10872 KB Output is correct
6 Correct 26 ms 10872 KB Output is correct
7 Correct 42 ms 12132 KB Output is correct
8 Correct 23 ms 12132 KB Output is correct
9 Correct 21 ms 12132 KB Output is correct
10 Correct 25 ms 12132 KB Output is correct
11 Correct 25 ms 12132 KB Output is correct
12 Correct 30 ms 12132 KB Output is correct
13 Correct 74 ms 13428 KB Output is correct
14 Correct 46 ms 14196 KB Output is correct
15 Correct 60 ms 15360 KB Output is correct
16 Execution timed out 117 ms 20748 KB Time limit exceeded
17 Execution timed out 240 ms 21900 KB Time limit exceeded
18 Runtime error 65 ms 27244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 79 ms 29676 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 52 ms 29676 KB Execution killed with signal 11 (could be triggered by violating memory limits)