「POJ2187」Beauty Contest

2015年1月25日8,1171

Description

Bessie, Farmer John’s prize cow, has just won first place in a bovine beauty contest, earning the title ‘Miss Cow World’. As a result, Bessie will make a tour of N (2 <= N <= 50,000) farms around the world in order to spread goodwill between farmers and their cows. For simplicity, the world will be represented as a two-dimensional plane, where each farm is located at a pair of integer coordinates (x,y), each having a value in the range -10,000 … 10,000. No two farms share the same pair of coordinates.Even though Bessie travels directly in a straight line between pairs of farms, the distance between some farms can be quite large, so she wants to bring a suitcase full of hay with her so she has enough food to eat on each leg of her journey. Since Bessie refills her suitcase at every farm she visits, she wants to determine the maximum possible distance she might need to travel so she knows the size of suitcase she must bring.Help Bessie by computing the maximum distance among all pairs of farms.

Input

* Line 1: A single integer, N* Lines 2..N+1: Two space-separated integers x and y specifying coordinate of each farm

Output

* Line 1: A single integer that is the squared distance between the pair of farms that are farthest apart from each other.

Sample Input

Sample Output

Hint

Farm 1 (0, 0) and farm 3 (1, 1) have the longest distance (square root of 2)

题解

旋转卡壳

旋转(zhuan4)卡(qia3)壳(ke2)是这么念的么2333

网上似乎教程都是这样:

旋转卡壳可以用于求凸包的直径、宽度,两个不相交凸包间的最大距离和最小距离等。虽然算法的思想不难理解,但是实现起来真的很容易让人“卡壳”。
拿凸包直径(也就是凸包上最远的两点的距离)为例,原始的算法是这样子:

  1. Compute the polygon’s extreme points in the y direction. Call them ymin and ymax.
  2. Construct two horizontal lines of support through ymin and ymax. Since this is already an anti-podal pair, compute the distance, and keep as maximum.
  3. Rotate the lines until one is flush with an edge of the polygon.
  4. A new anti-podal pair is determined. Compute the new distance, compare to old maximum, and update if necessary.
  5. Repeat steps 3 and 4 until the anti-podal pair considered is (ymin,ymax) again.
  6. Output the pair(s) determining the maximum as the diameter pair(s).

   更具体的可参见http://cgm.cs.mcgill.ca/~orm/rotcal.frame.html

直接按照这个描述可以实现旋转卡壳算法,但是代码肯定相当冗长。逆向思考,如果qa,qb是凸包上最远两点,必然可以分别过qa,qb画出一对平行线。通过旋转这对平行线,我们可以让它和凸包上的一条边重合,如图中蓝色直线,可以注意到,qa是凸包上离p和qb所在直线最远的点。于是我们的思路就是枚举凸包上的所有边,对每一条边找出凸包上离该边最远的顶点,计算这个顶点到该边两个端点的距离,并记录最大的值。直观上这是一个O(n2)的算法,和直接枚举任意两个顶点一样了。但是注意到当我们逆时针枚举边的时候,最远点的变化也是逆时针的,这样就可以不用从头计算最远点,而可以紧接着上一次的最远点继续计算(详细的证明可以参见上面链接中的论文)。于是我们得到了O(n)的算法。

其实直接看代码就好了T T

 

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
咸鱼 Recent comment authors
  Subscribe  
提醒
咸鱼
咸鱼

这个实现方式值得借鉴呀