Under construction

Still being built. Things may change

Triangle

Time limit1sMemory limit2048 MB

Summary
Pick one interior lattice point on each side of a lattice triangle and find the largest and smallest doubled area of the triangle they form, or -1.
Level

Medium5 of 10

Topics
Number theory, Geometry, Math
Solved
No attempts yet

Problem

There is a triangle whose three vertices AA, BB, and CC all have integer coordinates. Select one point with integer coordinates on each side of the triangle, and connect the three points to form a new triangle. When creating the new triangle, no vertex of the given triangle can be selected as a vertex of the new triangle.

Depending on which points you select, the area of the new triangle may be large or small. Write a program that finds the largest and smallest areas of the new triangle, if they exist.

For example, as shown in the figure below, if the coordinates of the three vertices of the given triangle are (4,8)(4, 8), (−8,−1)(-8, -1), and (7,−7)(7, -7), the yellow triangle in Fig. L.1(a) has the largest area among the triangles that satisfy the condition, and the blue triangle in Fig. L.1(b) has the smallest area.

There may be no point with integer coordinates on any side of the given triangle, in which case the triangle you are looking for does not exist.

It is guaranteed that the three given points are not on a straight line.

Input

The input consists of a single line with six integers AxA_x, AyA_y, BxB_x, ByB_y, CxC_x, and CyC_y, which are the coordinates of vertices A=(Ax,Ay)A = (A_x, A_y), B=(Bx,By)B = (B_x, B_y), and C=(Cx,Cy)C = (C_x, C_y), in that order. Each coordinate is an integer between −109-10^9 and 10910^9, inclusive.

Output

Let Smax⁡S_{\max} be the area of the new triangle with the largest area, and Smin⁡S_{\min} the area of the one with the smallest area. If such triangles exist, print 2Smax⁡2S_{\max} and 2Smin⁡2S_{\min} in that order, where both are positive integers. If no such triangle exists, print -1.

Examples3

  1. Example 1

    Input
    4 8 -8 -1 7 -7
    
    Expected output
    69 46
    
  2. Example 2

    Input
    -8 1 7 11 7 -5
    
    Expected output
    121 23
    
  3. Example 3

    Input
    0 0 1 10 10 0
    
    Expected output
    -1