100422024-03-25 18:44:00HVMarciHázakcpp17Hibás válasz 30/100138ms26512 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) {
	int f = fordul(origo, a, b);
	return f < 0 || f == 0 && (a.x*a.x + a.y*a.y) > (b.x*b.x + b.y*b.y);
}

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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1828 KiB
2Elfogadva13ms4720 KiB
subtask215/15
3Elfogadva3ms2248 KiB
4Elfogadva4ms2716 KiB
5Elfogadva8ms4184 KiB
6Elfogadva13ms5440 KiB
7Elfogadva14ms5560 KiB
subtask315/15
8Elfogadva3ms2744 KiB
9Elfogadva3ms3128 KiB
10Elfogadva3ms3468 KiB
11Elfogadva3ms3436 KiB
12Elfogadva4ms3916 KiB
subtask40/20
13Elfogadva4ms3720 KiB
14Hibás válasz4ms4268 KiB
15Elfogadva8ms5360 KiB
16Elfogadva10ms5816 KiB
17Elfogadva10ms5888 KiB
subtask50/50
18Hibás válasz25ms9344 KiB
19Elfogadva35ms10588 KiB
20Elfogadva64ms15264 KiB
21Elfogadva131ms26252 KiB
22Hibás válasz138ms26512 KiB