Submission #54946

#	Time	Username	Problem	Language	Result	Execution time	Memory
54946		linkret	Printed Circuit Board (CEOI12_circuit)	C++14	75 / 100	194 ms	29524 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;

	// 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 / 100