加墙数据

暴力思路：对于每条线，遍历其他所有线，看看能不能覆盖。

建议$n$开到1e7

#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
#define N 500005
using namespace std;
//#define MYBUF (1 << 20)
//char buf[MYBUF], *p1, *p2;
//#define getchar()                                                               \
//	(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MYBUF, stdin), p1 == p2)   \
//	 ? EOF                                                               \
//	 : *p1++)
inline int read() {
	int x=0,y=1;
	char e=getchar();
	while(e<'0'||e>'9') {
		if(e=='-')y=-1;
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<1)+(x<<3)+(e-'0');
		e=getchar();
	}
	return x*y;
}
int n;
struct node{
	int k,b;
}a[N]; 
bool die[N];
signed main() {
	R(n);
	for(int i=1;i<=n;++i){
		R(a[i].k),R(a[i].b);
	}
	for(int i=1;i<=n;++i){
		double l=-1000000000000,r=100000000000;
		for(int j=1;j<=n;++j){
			if(i==j)continue;
			int b1=a[i].b,b2=a[j].b,k1=a[i].k,k2=a[j].k;
			if(k1==k2){
				if(b1<b2){
					die[i]=1;
					break;
				}
				continue;
			}
			double x=(b2-b1)*1.0/(k1-k2);
			if(k1>0){
				if(k2>k1)r=min(r,x);
				else l=max(l,x);
			}else{
				if(k2<k1)l=max(l,x);
				else r=min(r,x);
			}
			if(l>=r){
				die[i]=1;
				break;
			}
		}
	}
	for(int i=1;i<=n;++i){
		if(!die[i]){
			cout<<i<<" ";
		}
	}
	return 0;
}