10118 2024. 03. 27 15:48:00 111 Házak cpp17 Elfogadva 100/100 141ms 28776 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

#define INF (int)1e8

int cross(int x1,int y1,int x2,int y2){
	return x1*y2-y1*x2;
}

int right(int x1,int y1,int x2,int y2,int x3,int y3){
	return cross(x1-x2,y1-y2,x3-x2,y3-y2)>=0;
}

struct P{
	int x,y;
	friend bool operator<(P a,P b){
		return a.y*b.x<b.y*a.x||a.y*b.x==b.y*a.x&&a.x<b.x;
	}
};

struct L{
	P l,h;
	friend bool operator<(L a,L b){
		int x=right(a.l.x,a.l.y,a.h.x,a.h.y,b.l.x,b.l.y)+right(a.l.x,a.l.y,a.h.x,a.h.y,b.h.x,b.h.y);
		int y=right(b.l.x,b.l.y,b.h.x,b.h.y,a.l.x,a.l.y)+right(b.l.x,b.l.y,b.h.x,b.h.y,a.h.x,a.h.y);
		return x>y;
	}
};

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N;
	cin>>N;
	vector<L>v(N+1);
	vector<pair<P,int>>w;
	for(int i=1;i<=N;i++){
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		v[i]={P{x2,y1},P{x1,y2}};
		w.emplace_back(P{x2,y1},-i);
		w.emplace_back(P{x1,y2},i);
	}
	sort(w.begin(),w.end());
	vector<int>ans(N+1);
	map<L,int>m;
	for(auto[_,i]:w){
		if(i<0){
			m[v[-i]]=-i;
		}
		else{
			m.erase(v[i]);
		}
		if(!m.empty()){
			ans[m.begin()->second]=1;
		}
	}
	cout<<count(ans.begin(),ans.end(),1)<<'\n';
	for(int i=1;i<=N;i++){
		if(ans[i]){
			cout<<i<<' ';
		}
	}
	cout<<'\n';
	return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1896 KiB
2 Elfogadva 14ms 4788 KiB
subtask2 15/15
3 Elfogadva 3ms 2752 KiB
4 Elfogadva 4ms 3300 KiB
5 Elfogadva 8ms 4592 KiB
6 Elfogadva 13ms 5784 KiB
7 Elfogadva 13ms 6196 KiB
subtask3 15/15
8 Elfogadva 3ms 3976 KiB
9 Elfogadva 3ms 3968 KiB
10 Elfogadva 3ms 4256 KiB
11 Elfogadva 3ms 4488 KiB
12 Elfogadva 4ms 4656 KiB
subtask4 20/20
13 Elfogadva 4ms 4688 KiB
14 Elfogadva 4ms 4908 KiB
15 Elfogadva 8ms 6280 KiB
16 Elfogadva 10ms 6532 KiB
17 Elfogadva 10ms 7004 KiB
subtask5 50/50
18 Elfogadva 26ms 10356 KiB
19 Elfogadva 35ms 12152 KiB
20 Elfogadva 64ms 17320 KiB
21 Elfogadva 125ms 28776 KiB
22 Elfogadva 141ms 28708 KiB