2015
04-13

# Pirates of the Caribbean

Let’s put our eyes on the Caribbean Sea, where the pirates are most active among all, and where our story occurs. This mysterious sea is located at the southeast side of the North America with beautiful blue sky, warm sunshine and crystal clear seawater. Here is a must-pass for those who wanted to reach America from Europe in 17th century, so the pirates are quite rampant back then. They attack the merchants, the passersby and even the royal armada of British.
The rule breaker, the undeterminable Nono, a young pirate recently appears actively at Caribbean Sea, with his terrifying pirate ship “Black Panda”, robs bamboos from merchant ships.

There are N islands in Caribbean Sea, numbered 1,2…N, the ith island is located at (xi, yi). In order to rob the merchant ships, Captain Nono travels among these N islands very often. Nono is very good at physics and math as they are basic surviving skills for pirates. For example, he knows that between two points, straight line is the shortest path. So he will choose the straight line as the path when he sails.
A (kx, ky) direction wind is blowing all the time, and the wind speed is a constant and is lower than the basic speed of the “Black Panda”. The real speed “Black Panda” produces is the vector sum of the wind-speed and the basic speed.
Now the problem is: Nono wants to know, among this N islands, what are the starting point and end point when “Black Panda” sails fastest.

The input has multiple cases (no more than 100). In each case, the first line contains three integers N, kx, ky, (1<N<10^5, -10^6 < kx, ky < 10^6) represent the number of islands and the direction of the wind. Following N lines, each line has two integers xi and yi (-10^6<xi, yi<10^6) represents the coordinate of the ith island. No two islands locate at the same place. Input terminates with EOF.

The input has multiple cases (no more than 100). In each case, the first line contains three integers N, kx, ky, (1<N<10^5, -10^6 < kx, ky < 10^6) represent the number of islands and the direction of the wind. Following N lines, each line has two integers xi and yi (-10^6<xi, yi<10^6) represents the coordinate of the ith island. No two islands locate at the same place. Input terminates with EOF.

3 1 1
0 0
1 1
2 3
3 1 0
0 0
-1 0
1 0
3 1 0
0 0
2 0
1 0

1 2
1 3
1 2

1. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

2. 问题3是不是应该为1/4 .因为截取的三段，无论是否能组成三角形， x， y-x ，1-y,都应大于0，所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

3. 这道题目虽然简单，但是小编做的很到位，应该会给很多人启发吧！对于面试当中不给开辟额外空间的问题不是绝对的，实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟，今天看到小编这篇文章相见恨晚。