Pro.ID21099 TitleArtemis Title链接http://10.20.2.8/oj/exercise/problem?problem_id=21099 AC0 Submit0 Ratio- 时间&空间限制描述Zeus gave Artemis, the goddess of the wilderness, a rectangular area for growing a forest. With the left side of the area as a segment of the positive y-axis and the bottom side as a segment of the positive x-axis, and (0,0) the left bottom corner of the area, Zeus told Artemis to plant trees only on integer coordinate points in the area. Artemis liked the forest to look natural, and therefore planted trees in such a way that a line connecting two trees was never parallel to x-axis or y-axis. At times, Zeus wants Artemis to cut trees for him. The trees are to be cut as follows:
As Artemis likes the trees, she wants to fulfill these conditions whilst cutting as few trees as possible. You are to write a program that, given information on the forest and the minimum number T of trees to be cut, selects an area for cutting trees for Artemis. 输入The input file name is artemis.in. The first line contains one integer N: the number of trees in the forest. The second line contains one integer T: the minimum number of trees to be cut. The following N lines describe the positions of the N trees. Each of these lines contains two integers X and Y: the x-coordinate followed by the y-coordinate of a tree. In all inputs, 1≤ N ≤ 20000, 0≤ X,Y ≤ 64000 and , 1 输出Description Zeus gave Artemis, the goddess of the wilderness, a rectangular area for growing a forest. With the left side of the area as a segment of the positive y-axis and the bottom side as a segment of the positive x-axis, and (0,0) the left bottom corner of the area, Zeus told Artemis to plant trees only on integer coordinate points in the area. Artemis liked the forest to look natural, and therefore planted trees in such a way that a line connecting two trees was never parallel to x-axis or y-axis. At times, Zeus wants Artemis to cut trees for him. The trees are to be cut as follows:
As Artemis likes the trees, she wants to fulfill these conditions whilst cutting as few trees as possible. You are to write a program that, given information on the forest and the minimum number T of trees to be cut, selects an area for cutting trees for Artemis. Input The input file name is artemis.in. The first line contains one integer N: the number of trees in the forest. The second line contains one integer T: the minimum number of trees to be cut. The following N lines describe the positions of the N trees. Each of these lines contains two integers X and Y: the x-coordinate followed by the y-coordinate of a tree. In all inputs, 1≤ N ≤ 20000, 0≤ X,Y ≤ 64000 and , 1 Output The output file name is artemis.out. The file is to contain one line with two integers I and J separated by one space: Artemis should use the Ith tree (with position given on line I+2 of the input file) and Jth tree (with position given on line J+2 of the input file) as the corners of the area for cutting trees. The order of these two number is irrelevant. There may be several ways to choose these trees and you need to find and output one of them. For all test cases at least one solution exists. Sample Input 3 2 1 1 2 3 5 6 Sample Output 1 2 Hint Special Judge Source 样例输入3 2 1 1 2 3 5 6 样例输出1 2 提示Special Judge 作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2024-9-21 17:49 , Processed in 0.017637 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
