「BZOJ1007」[HNOI2008] 水平可见直线

2014年2月24日6,3785

Description

Input

第一行为N(0 < N < 50000),接下来的N行输入Ai,Bi

Output

从小到大输出可见直线的编号,两两中间用空格隔开,最后一个数字后面也必须有个空格

Sample Input

3
-1 0
1 0
0 0

Sample Output

1 2

题解

算法比较直观,先按斜率排序,再将最小的两条线入栈,然后依次处理每条线,如果其与栈顶元素的交点在上一个点的左边,则将栈顶元素出栈 ;这样为什么对呢?因为对如任意一个开口向上的半凸包,从左到右依次观察每条边和每个顶点,发现其斜率不断增大,顶点的横坐标也不断增大。

 

说点什么

提醒
avatar
Erbhj

为什么crossx(a,st[top-1])<=crossx(st[top],st[top-1])可以判断交点在左边?

Sundes
Sundes

crossx求出两直线方程关于x的解.. 根据x坐标的大小就可以判断左右呀.

凹凸凹凸

擦,有人冒充我

hzy9819
hzy9819

黄学长刷的题好多。。但学长表示800道题足够进队了