1007: [HNOI2008]水平可见直线Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 4567 Solved: 1686
Description
在xoy直角坐标平面上有n条直线L1,L2,…Ln,若在y值为正无穷大处往下看,能见到Li的某个子线段,则称Li为可见的,否则Li为被覆盖的. 例如,对于直线: L1:y=x; L2:y=-x; L3:y=0 则L1和L2是可见的,L3是被覆盖的. 给出n条直线,表示成y=Ax+B的形式(|A|,|B|<=500000),且n条直线两两不重合.求出所有可见的直线.
Input
第一行为N(0 < N < 50000),接下来的N行输入Ai,Bi
Output
从小到大输出可见直线的编号，两两中间用空格隔开,最后一个数字后面也必须有个空格
Sample Input
3-1 01 00 0
Sample Output
1 2
题解：
第一眼我觉得这是一个半平面交，然而仔细看题后发现其实没那么复杂，只需要维护一个下凸壳就好了。
Code：
;#define N 50100struct E{int xu,a,b;}e[N],ee[N];int n,top=0,num=0,z[N];int in(){int x=0; char ch=getchar(); bool f=true;while (ch<‘0′ || ch>’9′){if (ch==’-‘) f=false;ch=getchar();}while (ch>=’0′ && ch<=’9’) x=x*10+ch-‘0’,ch=getchar();if (!f) x=-x;return x;}bool cmp1(E x,E y){return x.a>y.a;}bool cmp2(int x,int y){return ee[x].xu<ee[y].xu;}double jiao(E x,E y){return (double)((double)(y.b-x.b)/(double)(x.a-y.a));}int main(){n=in(); z[++top]=1;for (int i=1; i<=n; i++)e[i].xu=i,e[i].a=in(),e[i].b=in();sort(e+1,e+n+1,cmp1);for (int i=1; i<=n; i++){if (e[i].a!=ee[i-1].a) ee[++num]=e[i];else if (e[i].b>ee[num].b) ee[num]=e[i];}for (int i=2; i<=num; i++){while (top>=2){double x1=jiao(ee[z[top-1]],ee[i]);double x2=jiao(ee[z[top]],ee[i]);if (x1<=x2+1e-6) top–;else break;}z[++top]=i;}sort(z+1,z+top+1,cmp2);for (int i=1; i<=top; i++) printf(“%d “,ee[z[i]].xu);return 0;}
，我知道有一种爱情，叫做与你白头，有一种幸福，叫做和你相伴。
