同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

21099_Artemis

2022-5-16 18:18| 发布者: Hocassian| 查看: 45| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504837560100-Problem List-采集的数据-后羿采集器.html

Pro.ID

21099

Title

Artemis

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=21099

AC

Submit

Ratio

时间&空间限制

Time Limit: 1500/500 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)

描述

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:

Zeus wants at least a given number T of trees to be cut for him.
To get a rectangular football pitch for future football success, Artemis is to cut all trees within a rectangular area, and no trees outside of it.
The sides of this rectangular area are to be parallel to x-axis and y-axis.
Two opposite corners of the area must be located on trees and therefore those corner trees are also cut.

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 wants at least a given number T of trees to be cut for him.
To get a rectangular football pitch for future football success, Artemis is to cut all trees within a rectangular area, and no trees outside of it.
The sides of this rectangular area are to be parallel to x-axis and y-axis.
Two opposite corners of the area must be located on trees and therefore those corner trees are also cut.

Input

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

IOI 2004