100432024-03-25 18:50:27HVMarciHázakcpp17Wrong answer 30/100138ms25720 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1980 KiB
2Accepted13ms4892 KiB
subtask215/15
3Accepted3ms2272 KiB
4Accepted4ms2880 KiB
5Accepted8ms4216 KiB
6Accepted13ms5580 KiB
7Accepted13ms5792 KiB
subtask315/15
8Accepted3ms3304 KiB
9Accepted3ms3420 KiB
10Accepted3ms3452 KiB
11Accepted3ms3720 KiB
12Accepted3ms3876 KiB
subtask40/20
13Accepted4ms4096 KiB
14Wrong answer4ms4384 KiB
15Accepted8ms5540 KiB
16Accepted10ms5696 KiB
17Accepted10ms5692 KiB
subtask50/50
18Wrong answer25ms9156 KiB
19Accepted35ms10044 KiB
20Accepted64ms14732 KiB
21Accepted128ms25720 KiB
22Wrong answer138ms25720 KiB