100412024-03-25 18:40:26HVMarciHázakcpp17Wrong answer 30/100134ms35880 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define INF (LLONG_MAX/2)
#pragma GCC optimize ("O3")

struct pont {
	int x, y, i;
} origo = {0, 0, 0};

struct szakasz {
	pont p, q;
};

int fordul(const pont& a, const pont& b, const pont& c) {
	return (c.x - a.x) * (b.y - a.y) - (c.y - a.y) * (b.x - a.x);
}

bool polarr(const pont& a, const pont& b) {
	return fordul(origo, a, b) < 0;
}

vector<szakasz> szakaszok;
bool scomp(int a, int b) {
	//cout << "comp" << endl;
	//return a < b;
	//cout << szakaszok[a].p.i << " comp" << endl;
	return fordul(szakaszok[a].p, szakaszok[a].q, szakaszok[b].p) > 0;
}

signed main() {
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    int n;
	cin >> n;

	vector<pont> pontok;
	szakaszok.resize(n + 1);
	vector<bool> latszik(n + 1, false);

	for (int i = 1; i <= n; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;

		pont p{a, d, -i}, q{c, b, i};

		pontok.push_back(p);
		pontok.push_back(q);

		szakaszok[i] = {q, p};
	}

	sort(pontok.begin(), pontok.end(), polarr);

	//cout << pontok[0].x << " " << pontok[0].y << endl;

	int ans = 0;
	set<int, decltype(scomp)*> sp(scomp);

	for (pont& p : pontok) {
		//cout << sp.size() << endl;
		if (p.i > 0) {
			sp.insert(p.i);
			//cout << p.i << endl;
		} else {
			sp.erase(-p.i);
		}

		//cout << "," << *sp.begin() << endl;
		if (!sp.empty() && !latszik[*sp.begin()]) {
			//cout << *sp.begin() << endl;
			ans++;
			latszik[*sp.begin()] = true;
		}
	}

	cout << ans << endl;
	for (int i = 1; i <= n; i++) {
		if (latszik[i]) cout << i << " ";
	}
	cout << endl;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1952 KiB
2Accepted14ms5292 KiB
subtask215/15
3Accepted3ms2868 KiB
4Accepted4ms3428 KiB
5Accepted8ms4700 KiB
6Accepted13ms6212 KiB
7Accepted13ms6580 KiB
subtask315/15
8Accepted3ms3916 KiB
9Accepted3ms4208 KiB
10Accepted3ms4300 KiB
11Accepted3ms4608 KiB
12Accepted4ms5056 KiB
subtask40/20
13Accepted4ms4940 KiB
14Wrong answer4ms5164 KiB
15Accepted8ms6568 KiB
16Accepted10ms7196 KiB
17Accepted10ms7424 KiB
subtask50/50
18Wrong answer24ms11596 KiB
19Accepted34ms13412 KiB
20Accepted64ms19544 KiB
21Accepted126ms32728 KiB
22Wrong answer134ms35880 KiB