相隔近两月才来写这篇报告，估计大家早没有兴趣听这个题目了。最近一直在赶paper的档期，实在是静不下来写一些东西，恐怕这样的状态还要持续好一阵。

先回顾一下题目。一个图，每个点x有两个值f(x)和g(x)。两点x和y之间的距离定义为：d = ( f(y)-f(x) )/( g(y)-g(x) )。现在要往图里面添加边，规则如下：

1. 从所有异于x的点中选取一个顶点y，使得y到x的距离d是所有点中最小的，并且d >≥0。如果有多种选择，则选abs(f(y)-f(x))最小的一个(abs(t)表示取t的绝对值)，如果有多个abs(f(y)-f(x))相等，则选择f(y)-f(x)>0的那个点；

2. 添加无向边(x, y)（如果这条边已经存在，则不重复添加）。

现在要回答问题，每个问题询问x和y是否存在一条path。

大家都能很快看出，此题的后半部分就是一个并查集，难处主要在前半部分：这个图中哪两点间有边？因为题目的规模是有50,000个顶点，所以一个直接的O(n^2)算法是不行的。

其实，该题的障眼法我觉得设计得还是不够好：一看那个求d的公式，大家就基本上都猜到这个问题肯定和斜率有关。再加上题目的tips中说每个点的f和g值都不相同，于是基本上就可以确定这个题是一个计算几何了。

我坦白，这个问题其实就是要在平面n个点找形成直线后斜率最大的点对。首先把求d的那个公式倒过来一下，于是就变成了求1/d最大的问题。我们设每个点x的坐标为( f(x), g(x) )，很自然的把这些点表示出来。

然后就是把它们按照X坐标从小到大排序了。因为我们要求的是d ≥ 0（自然1/d ≥ 0）的直线，自然对每个点，只需要考虑如果以它为原点建坐标系，那么在1，3象限中的那些点。由于1和3象限的对称性，我们只说明1象限怎么做。

我们按照X坐标从大到小的顺序访问这些点。现在我们考察点x。我们用T(x)表示那些在X坐标比x大的那些点。如果要从T(x)找一个点y出来和x连线得到的斜率最大，那y肯定要是T(x)形成的凸包的上半部分。这个证明比较容易，因为假设y在凸包内部，那么我们知道x和y的连线一定和凸包上的某条边E相交了。设E的两个顶点是e1和e2，其中e1的Y坐标大于e2的Y坐标。那么我们可以知道，选择e1和x连线一定不会比选择y连线得到的直线斜率小。于是得到y应该从凸包上取。

有了这个分析，下一步就是如何从凸包上去找到y。很巧的是，这里面有个单调性，利用它可以设计巧妙的算法，见下图：

其中e1 – e5是凸包上的点，然后L1 – L5是x到这些点的连线。可能一个很直观的感受是，只要选凸包上Y值最大的点就行，于是上面的图就可以选出e3来。但其实不然，比如下图：

这就像一个人站在X处打探，e1和e2是两座山顶，那他肯定无法看到e2（即X – e1的斜率大于X – e2的斜率）。从数学的角度来描述这个事实非常容易：线段e2 – e1和e1 – X的叉积大于等于0。

于是，我们可以通过枚举凸包上连续的两点e1和e2，然后做一个叉积：如果大于0，我们知道e2和e2右边的所有点都被e1挡住了（因为上凸包的左转性质很容易证明）。于是这个单调性就很明显了：

如果e1挡住了其后面的点的“视线”，那么可知要找的最优点y一定是e1或者e1左边的点。依次，我们可以设计一个简单的二分算法来枚举凸包上的点，这样就可以使得求最优点的每步操作提高到lgn。

当然，计算几何题最烦人的地方就在于细节很多。以上给出了主要的思路，剩下的细节就大家自己想想。其实现在来看，C题明显比B的思路要简单，而且编程也不会更复杂。我本来也以为B应该是整套题最难的。不过从当时比赛的结果来看，大家似乎都只对B感兴趣，而忽略了C，我想主要还是因为B看起来要熟悉一些，而在比赛中一般都比较喜欢偷懒，有做过的题自然就要先照顾了。

夜深，剩下的一篇花絮希望尽快补上，不要再拖两个月-_-~~。