#P15488. [IOI 2004] Artemis
[IOI 2004] Artemis
说明
宙斯给了旷野女神阿尔忒弥斯一块长方形的地来种一片森林。
将这块地的左侧作为 轴正半轴,底部作为 轴正半轴,以及这块地的左下角作为 。
宙斯让阿尔忒弥斯只在这块地的整数坐标点上种树。阿尔忒弥斯喜欢让森林看起来很自然,因此种植树木的方式是,保证两棵树的连线永远不会平行于 轴或 轴。
有时,宙斯希望阿尔忒弥斯为他砍树。树木将按如下方式砍伐:
- 给定 ,宙斯希望至少为他砍伐 棵树,
- 为了获得一个矩形球场,阿尔忒弥斯要砍伐一个矩形区域内的所有树木,而不砍这个矩形区域外的树木,
- 该矩形区域的边应平行于 轴和 轴,
- 该区域的两个相对角落必须位于树木上,因此这些角落的树木也会被砍伐。
由于阿尔忒弥斯喜欢这些树,她希望在尽可能少砍伐树木的同时满足这些条件。您需要编写一个程序,根据森林信息和要砍伐的最小树木数量 ,为阿尔忒弥斯选择一个砍伐树木的区域。
输入格式
第一行一个整数 :森林里的树的数量。
第二行一个整数 :被砍伐的树的最小数量。
接下来 行描述了 棵树的位置。每行两个整数 和 :树的 坐标和 坐标。
输出格式
一行两个整数 和 ,用一个空格分隔:阿尔忒弥斯应使用第 棵树(位于输入文件的 行)和第 棵树(位于输入文件的 行)作为砍伐树木的区域的角。这两个数字的顺序不重要。
可能有多种方法选择这些树,您需要找到并输出其中一种。对于所有测试用例,至少存在一个解决方案。
3
2
1 1
2 3
5 6
1 2
提示
在所有测试点中,,,。
此外,在 的测试点中,。
京公网安备 11011102002149号