题目大意：给出一些笛卡尔系中的一些直线，问从(0,+∞)向下看时能看到哪些直线。
思路：半平面交可做，可是显然用不上。
类似于求凸包的思想，维护一个栈。
先将全部直线依照k值排序。然后挨个压进去，遇到有前一个交点被挡住的话就先弹栈。
比較闹心的是去重。我的方法是压栈之前先去重，然后在处理。
CODE：
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 50010
#define EPS 1e-5
using namespace std;inline bool dcmp(double a,double b);struct Point{double x,y;Point(double _ = 0,double __ = 0):x(_),y(__) {}Point operator +(const Point &a)const {return Point(x + a.x,y + a.y);}Point operator -(const Point &a)const {return Point(x - a.x,y - a.y);}
};
struct Line{double k,b;int _id;bool operator <(const Line &a)const {if(dcmp(k,a.k)) return b < a.b;return k < a.k;}
}line[MAX],_line[MAX];int lines;
int top;
Line *stack[MAX];
Point intersection[MAX];bool ans[MAX];inline Point GetIntersection(const Line &l1,const Line &l2);
inline bool Under(const Line &l,const Point &p);int main()
{cin >> lines;for(int i = 1;i <= lines; ++i) {scanf("%lf%lf",&line[i].k,&line[i].b);line[i]._id = i;}sort(line + 1,line + lines + 1);int cnt = 0;for(int i = 1;i <= lines; ++i) {if(dcmp(line[i].k,line[i + 1].k)) continue;_line[++cnt] = line[i];}stack[++top] = &_line[1];stack[++top] = &_line[2];intersection[top - 1] = GetIntersection(_line[1],_line[2]);for(int i = 3;i <= cnt; ++i) {if(i != cnt && _line[i].k == _line[i + 1].k) continue;while(top > 1 && Under(_line[i],intersection[top - 1])) --top;stack[++top] = &_line[i];intersection[top - 1] = GetIntersection(*stack[top],*stack[top - 1]);}for(int i = 1;i <= top; ++i)ans[stack[i]->_id] = true;for(int i = 1;i <= lines; ++i)if(ans[i]) printf("%d ",i);return 0;
}inline bool dcmp(double a,double b)
{return fabs(a - b) < EPS;
}inline Point GetIntersection(const Line &l1,const Line &l2)
{Point re;re.x = (l2.b - l1.b) / (l1.k - l2.k);re.y = re.x * l1.k + l1.b;return re;
}inline bool Under(const Line &l,const Point &p)
{if(l.k * p.x + l.b > p.y || dcmp(l.k * p.x + l.b,p.y)) return true;return false;
}