← 返回题目列表

Codeforces · 1019/D

D. 大三角形

中文机器翻译题面 查看原题

来自俄罗斯和国外许多不同地区的学生来到夏季信息学学校。您在地图上标记了 SIS 参与者的家乡。

现在您决定根据此地图准备一个有趣的信息图。您选择做的第一件事是在这张地图上找到三个城市,使它们形成一个面积为 $$$S$$$ 的三角形。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$S$$$ ($$$3 \le n \le 2000$$$, $$$1 \le S \le 2 \cdot 10^{18}$$$) — 地图上的城市数量和要查找的三角形的面积。

接下来的 $$$n$$$ 行包含城市的描述,每行一个。每个城市由其整数坐标 $$$x_i$$$、$$$y_i$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$) 描述。

保证所有城市都位于不同的点。还保证没有三个城市位于同一条线上。

输出

如果解不存在 — 打印“No”。

否则,打印“Yes”,后跟三对坐标 $$$(x, y)$$$ — 三个城市的位置,形成区域 $$$S$$$ 的三角形。

示例

输入 #1

3 7
0 0
3 0
0 4

输出 #1

No

输入 #2

4 3
0 0
2 0
1 2
1 3

输出 #2

Yes
0 0
1 3
2 0