10041 2024. 03. 25 18:40:26 HVMarci Házak cpp17 Hibás válasz 30/100 134ms 35880 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1952 KiB
2 Elfogadva 14ms 5292 KiB
subtask2 15/15
3 Elfogadva 3ms 2868 KiB
4 Elfogadva 4ms 3428 KiB
5 Elfogadva 8ms 4700 KiB
6 Elfogadva 13ms 6212 KiB
7 Elfogadva 13ms 6580 KiB
subtask3 15/15
8 Elfogadva 3ms 3916 KiB
9 Elfogadva 3ms 4208 KiB
10 Elfogadva 3ms 4300 KiB
11 Elfogadva 3ms 4608 KiB
12 Elfogadva 4ms 5056 KiB
subtask4 0/20
13 Elfogadva 4ms 4940 KiB
14 Hibás válasz 4ms 5164 KiB
15 Elfogadva 8ms 6568 KiB
16 Elfogadva 10ms 7196 KiB
17 Elfogadva 10ms 7424 KiB
subtask5 0/50
18 Hibás válasz 24ms 11596 KiB
19 Elfogadva 34ms 13412 KiB
20 Elfogadva 64ms 19544 KiB
21 Elfogadva 126ms 32728 KiB
22 Hibás válasz 134ms 35880 KiB