10347 2024. 03. 31 21:07:14 szil Házak cpp17 Elfogadva 100/100 141ms 44936 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct Point {
	ll x, y;
};

struct Line {
	Point a, b;
	int idx;
};

struct Event {
	Point ord;
	Line line;
	bool add;
	int idx;
};

const int MAXN = 100'001;

bool ans[MAXN];

Point operator+(Point a, Point b) {
	return {a.x + b.x, a.y + b.y};
}

Point operator-(Point a, Point b) {
	return {a.x - b.x, a.y - b.y};
}

ll cross(Point a, Point b) {
	return a.x * b.y - a.y * b.x;
}

int forog(Point a, Point b, Point c) {
	ll x = cross(b - a, c - a);
	if (x > 0) return 1;
	if (x == 0) return 0;
	if (x < 0) return -1;
}

bool operator<(const Line &a, const Line &b) {
	return forog(a.a, a.b, b.a) > 0;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	vector<Line> lines(n);
	vector<Event> events;
	for (Line &l : lines) {
		cin >> l.a.x >> l.b.y >> l.b.x >> l.a.y;
	}
	
	for (int i = 0; i < n; i++) {
		Event e1, e2;
		e1.line = e2.line = lines[i];
		e1.ord = lines[i].a;
		e2.ord = lines[i].b;
		e1.add = false;
		e2.add = true;
		e1.idx = e2.idx = i;
		events.emplace_back(e1);
		events.emplace_back(e2);
	}

	sort(events.begin(), events.end(), [&](auto a, auto b){
		ll forgas = cross(a.ord, b.ord);
		if (forgas == 0) {
			if (a.add != b.add) return a.add > b.add;
			return a.ord.x*a.ord.x + a.ord.y*a.ord.y < b.ord.x*b.ord.x + b.ord.y*b.ord.y;
		}
		return forgas > 0;
	});

	set<Line> s;
	for (auto [ord, line, add, idx] : events) {
		line.idx = idx;
		if (add) {
			s.insert(line);
		} else {
			auto it = s.find(line);
			assert(it != s.end());
			s.erase(it);
		}
		if (!s.empty()) ans[s.begin()->idx] = true;
	}

	cout << count(ans, ans+MAXN, true) << "\n";
	for (int i = 0; i < n; i++) {
		if (ans[i]) cout << i+1 << " ";
	}
	cout << "\n";

	return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1832 KiB
2 Elfogadva 14ms 7212 KiB
subtask2 15/15
3 Elfogadva 3ms 2456 KiB
4 Elfogadva 4ms 2820 KiB
5 Elfogadva 8ms 4836 KiB
6 Elfogadva 14ms 7616 KiB
7 Elfogadva 14ms 7824 KiB
subtask3 15/15
8 Elfogadva 3ms 3040 KiB
9 Elfogadva 3ms 3444 KiB
10 Elfogadva 3ms 3768 KiB
11 Elfogadva 3ms 3824 KiB
12 Elfogadva 4ms 4336 KiB
subtask4 20/20
13 Elfogadva 4ms 4480 KiB
14 Elfogadva 4ms 4912 KiB
15 Elfogadva 8ms 6704 KiB
16 Elfogadva 12ms 6980 KiB
17 Elfogadva 12ms 7144 KiB
subtask5 50/50
18 Elfogadva 28ms 14124 KiB
19 Elfogadva 37ms 14824 KiB
20 Elfogadva 67ms 24672 KiB
21 Elfogadva 135ms 44844 KiB
22 Elfogadva 141ms 44936 KiB