101182024-03-27 15:48:00111Házakcpp17Accepted 100/100141ms28776 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1896 KiB
2Accepted14ms4788 KiB
subtask215/15
3Accepted3ms2752 KiB
4Accepted4ms3300 KiB
5Accepted8ms4592 KiB
6Accepted13ms5784 KiB
7Accepted13ms6196 KiB
subtask315/15
8Accepted3ms3976 KiB
9Accepted3ms3968 KiB
10Accepted3ms4256 KiB
11Accepted3ms4488 KiB
12Accepted4ms4656 KiB
subtask420/20
13Accepted4ms4688 KiB
14Accepted4ms4908 KiB
15Accepted8ms6280 KiB
16Accepted10ms6532 KiB
17Accepted10ms7004 KiB
subtask550/50
18Accepted26ms10356 KiB
19Accepted35ms12152 KiB
20Accepted64ms17320 KiB
21Accepted125ms28776 KiB
22Accepted141ms28708 KiB