IOI '04 P2 - Artemis

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 16M

Problem type
IOI '04 - Athens, Greece

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:

  1. Zeus wants at least a given number T of trees to be cut for him.
  2. 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.
  3. The sides of this rectangular area are to be parallel to x-axis and y-axis.
  4. 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.

Input Specification

The first line contains one integer N (1 \le N \le 20\,000): the number of trees in the forest. The second line contains one integer T (1 < T \le N): 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 (0 \le X,Y \le 64\,000): the x-coordinate followed by the y-coordinate of a tree.

Output Specification

The output is to contain one line with two integers I and J separated by one space: Artemis should use the I-th tree (with position given on line I+2 of the input file) and J-th 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 numbers 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

1 1
2 3
5 6

Sample Output

1 2

Note: in 50\% of the inputs, 1 < N < 5\,000.


There are no comments at the moment.