当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

3881: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.
输出解释
For each case, output two integers x and y, separate by one space, represents when sails from x to y, “Black Panda” reaches highest speed. If multiple solutions exist, output the one with smallest x, and if still have multiple solutions, output the one with smallest y.
输入样例
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
来自杭电HDUOJ的附加信息
Author temperlsyer 51isoft
Recommend lcy

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-3881

最后修改于 2020-10-25T23:07:51+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
6000/3000MS(Java/Others) 65768/32768K(Java/Others)