#1138. ddd和鹦鹉

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Rhodoks

题目描述

ddd\text{ddd}在家憋坏了,于是他决定去动物园玩,但他并不知道动物园的具体位置,只知道在三角形ABCABC的范围内(包括边界与顶点)。

幸运的是ddd\text{ddd}养了只喜欢到处乱飞的鹦鹉,它肯定知道动物园在哪。ddd\text{ddd}铺开一张地图,在地图上画出了三个顶点A,B,CA,B,C。随后鹦鹉开始大叫:”3OA+2OB+OC3|OA|+2|OB|+|OC|最小!3OA+2OB+OC3|OA|+2|OB|+|OC|最小!“。

显然动物园的位置在满足3OA+2OB+OC3|OA|+2|OB|+|OC|最小的点OO处。同时ddd\text{ddd}还知道,O,A,B,CO,A,B,C均为整点。那么动物园究竟在哪儿呢?

输入格式

输入数据仅一行六个整数Ax,Ay,Bx,By,Cx,CyA_x,A_y,B_x,B_y,C_x,C_y,分别代表A,B,CA,B,C点的横纵坐标。

输出格式

输出两个整数Ox,OyO_x,O_y,为OO点的坐标,如果有多个满足题意的解,则输出任意一个即可。

样例

样例输入

0 1 0 0 2 0

样例输出

0 1

样例解释

三角形中的整点共有4个:(0,1),(0,0),(1,0),(2,0) 其中,(0,1)点作为点OO可使得3OA+2OB+OC3|OA|+2|OB|+|OC|取得最小值。

数据范围与提示

103Ax,Ay,Bx,By,Cx,Cy103-10^3 \leq A_x,A_y,B_x,B_y,C_x,C_y \leq 10^3