oj.uz

Submission #54943

# Submission time Handle Problem Language Result Execution time Memory
54943 2018-07-05T14:02:16 Z linkret Printed Circuit Board (CEOI12_circuit) C++14
75 / 100
 100 ms 29592 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 14 ms 9704 KB Output is correct
3 Correct 13 ms 10136 KB Output is correct
4 Correct 14 ms 10212 KB Output is correct
5 Correct 25 ms 10996 KB Output is correct
6 Correct 21 ms 10996 KB Output is correct
7 Correct 36 ms 12208 KB Output is correct
8 Correct 23 ms 12208 KB Output is correct
9 Correct 21 ms 12208 KB Output is correct
10 Correct 23 ms 12208 KB Output is correct
11 Correct 23 ms 12208 KB Output is correct
12 Correct 38 ms 12208 KB Output is correct
13 Correct 62 ms 13580 KB Output is correct
14 Correct 54 ms 14264 KB Output is correct
15 Correct 56 ms 15460 KB Output is correct
16 Execution timed out 101 ms 20836 KB Time limit exceeded
17 Execution timed out 167 ms 21856 KB Time limit exceeded
18 Runtime error 55 ms 27320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 69 ms 29592 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 60 ms 29592 KB Execution killed with signal 11 (could be triggered by violating memory limits)