#462. 三角形

三角形

题目描述

在三角形ABCABC的范围内(包括边界与顶点)给定了三个顶点A,B,CA,B,C

求满足3OA+2OB+OC3|OA|+2|OB|+|OC|最小的点OO处。

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