题解 P3081 【[USACO13MAR]山走Hill Walk】
先推销一下自己的博客：http://www.cnblogs.com/luyouqi233/p/8405865.html
首先说一下解题思路：我们走一遍线段，并且在掉落的时候以O(logn)的速度查找到你应当掉落在那个线段上。那么复杂度就是O(nlogn)了。
一个显然的思路，我们记录当前走在了哪个线段，用set维护接下来可能走的线段，取出我们所要的线段即可。
（PS：“可能”指你所在的坐标的x在某个线段的x区间内）
走在哪个线段没有难度，开个变量记录一下即可。
找接下来可能走的线段（并且及时剔除掉走过/不能走到的线段），扫描线即可解决。
那么这题的难点就在于我们如何排序（也就是set的比较方法）来取出我们所要的线段。
先画个图感性理解一下，黑点是我们所在的位置，编号就是我们排好序之后的编号。
（我们所在的位置是3，显然只需要跳到3-1=2的编号的那条边，我们就实现了走的动作。）
设比较的两条线段a,b，则分为两种情况：
1.ax2<bx2（eg：a=5,b=4或a=2,b=4）：
我们把a的右端点和b的左端点连线，显然发现这条线段将这两条线划分开来，上面的线编号大，下面的线编号小。
2.ax2>bx2（eg：a=1,b=3或a=4,b=3）：
同1的思路，其实只是把a和b颠倒而已。
我们可以通过斜率来比较两条线的位置。
（PPS：貌似可以两条线分别取一个不同方向的点连线貌似就可以，不必非得按照题解的连线方法）
（PPPS：可能有这种情况（举一个1的例子）：
这时候我们只需要平移一下就好了。
所以用斜率判断是最准确的。）