题目大意：给出一些笛卡尔系中的一些直线，问从(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;
}