#P2173. Cricket Field

    ID: 1174 远端评测题 1000ms 64MiB 尝试: 4 已通过: 1 难度: 10 上传者: 标签>数据结构计算几何Northeastern Europe 2002

Cricket Field

本题没有可用的提交语言。

题目

从前,有一位贪婪的国王,他命令首席建筑师在他的公园里为皇家板球运动建造一个场地。国王极其贪婪,根本不听从建筑师的建议,建筑师提议在公园中心建造场地,在其周围精心栽种树木,形成宜人的图案,并且在树间小道设置供观众行走的优美步道。相反,国王下令在公园里既不许砍伐也不许栽种哪怕一棵树木,但却要求为了他的享乐,建造一个尽可能大的板球场地。如果国王发现建筑师胆敢触碰公园里的任何一棵树木,或者设计的场地小于本可达到的最大规模,那么建筑师就会掉脑袋。此外,他要求建筑师立即拿出场地的规划,标明其确切位置和大小。 你的任务是帮助可怜的建筑师保住脑袋,编写一个程序,找出满足国王要求的板球场地的最大可能规模及其在公园内的位置。 $这个任务在一定程度上得到了简化,因为国王的公园呈矩形,且位于平坦的地面上。而且,公园的边界与南北和东西方向的线条完美对齐。同时,皇家板球运动总是在一个同样与南北和东西方向线条对齐的正方形场地上进行。建筑师已经建立了一个笛卡尔坐标系,并且精确测量了每棵树的坐标。当然,这个坐标系也是与南北和东西方向线条对齐的。公园的西南角坐标为 (0, 0),东北角坐标为 (W, H),其中 W 和 H 分别是公园的宽度和高度(单位:英尺)。$ 对于这个任务,你可以忽略树木的直径。树木不能位于板球场地内部,但可以位于场地的边上。板球场地也可以与公园边界接触,但不得超出公园范围。

输入

输入的第一行包含三个整数 N、W 和 H,用空格分隔。N0N100N(0 ≤ N ≤ 100)是公园内树木的数量。W 和 H(1 ≤ W, H ≤ 10000)分别是公园的宽度和高度(单位:英尺)。 $接下来的 N 行描述了公园内树木的坐标。每行包含两个用空格分隔的整数 Xi 和 Yi(0 ≤ Xi ≤ W,0 ≤ Yi ≤ H),表示第 i 棵树的坐标。所有树木的坐标都不同。$

输出

向输出写入一行,包含三个用空格分隔的整数 PQLP、Q 和 L,其中 (P,Q)(P, Q) 是板球场地西南角的坐标,LL 是场地边长。如果存在多个具有最大规模的场地位置,输出任意一个即可。