CF1019D.Large Triangle
省选/NOI-
通过率:0%
时间限制:3.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
There is a strange peculiarity: if you connect the cities of Rostov, Taganrog and Shakhty, peculiarly, you get a triangle
«Unbelievable But True»
Students from many different parts of Russia and abroad come to Summer Informatics School. You marked the hometowns of the SIS participants on a map.
Now you decided to prepare an interesting infographic based on this map. The first thing you chose to do is to find three cities on this map, such that they form a triangle with area S.
存在一种奇特的现象:若将罗斯托夫、塔甘罗格和沙赫蒂这三座城市连接起来,奇妙的是,它们恰好构成一个三角形。
《难以置信,但却是事实》
来自俄罗斯各地及海外的众多学生参加暑期信息学学校(SIS)。你已在地图上标出了所有SIS参与者的家乡。
现在,你决定基于这张地图制作一幅有趣的资讯图。你首先选择完成的任务是:在该地图上找出三座城市,使其构成面积为 S 的三角形。
输入格式
The first line of input contains two integers n and S (3≤n≤2000, 1≤S≤2⋅1018) — the number of cities on the map and the area of the triangle to be found.
The next n lines contain descriptions of the cities, one per line. Each city is described by its integer coordinates xi, yi (−109≤xi,yi≤109).
It is guaranteed that all cities are located at distinct points. It is also guaranteed that no three cities lie on the same line.
输入的第一行包含两个整数 n 和 S(3≤n≤2000,1≤S≤2⋅1018)—— 分别表示地图上的城市数量以及待寻找的三角形面积。
接下来的 n 行每行描述一座城市。每座城市由其整数坐标 xi、yi(−109≤xi,yi≤109)描述。
保证所有城市均位于互不相同的点上,且任意三个城市均不共线。
输出格式
If the solution doesn't exist — print «No».
Otherwise, print «Yes», followed by three pairs of coordinates (x,y) — the locations of the three cities, which form the triangle of area S.
如果不存在解,则输出 «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
输入解题思路,AI测评打分。不知道怎么写?