题目大意:

;

题解

其实就是求每条直线的上半部分的交

所以做裸半平面交即可

#include 
    
     #include 
     
      #include 
      
       using namespace std;typedef long long ll;inline void read(int &x){    x=0;char ch;bool flag = false;    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;    while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;}inline int cat_max(const int &a,const int &b){return a>b ? a:b;}inline int cat_min(const int &a,const int &b){return a
        -eps) return 0;    return x > 0 ? 1 : -1;}struct Point{    double x,y;    Point(){}    Point(const double &a,const double &b){x=a;y=b;}    void print(){        printf("%lf %lf\n",x,y);    }};struct line{    double k,b;    int id;};inline bool cmp(const line &a,const line &b){    return dcmp(a.k-b.k) == 0 ? a.b > b.b : a.k < b.k;}inline bool kmp(const line &a,const line &b){    return a.id < b.id;}inline Point Interion(const line &x,const line &y){    double t = (y.b - x.b)/(x.k - y.k);    return Point(t,x.k*t+x.b);}line lines[maxn],sta[maxn];int top = 0;int main(){    int n;read(n);    for(int i=1;i<=n;++i){        scanf("%lf%lf",&lines[i].k,&lines[i].b);        lines[i].id = i;    }sort(lines+1,lines+n+1,cmp);    for(int i=1;i<=n;++i){        if(dcmp(lines[i].k-sta[top].k) == 0) continue;        while(top >= 2){            Point x = Interion(lines[i],sta[top]);            Point y = Interion(sta[top],sta[top-1]);            if(dcmp(x.x-y.x) <= 0) --top;            else break;        }sta[++top] = lines[i];    }sort(sta+1,sta+top+1,kmp);    for(int i=1;i<=top;++i) printf("%d ",sta[i].id);    getchar();getchar();    return 0;}