50043. Mosaics

I'm a slow walker, but I never walk backwards.

Task Description

A 2D space is fully covered by $1 \times 1$ mosaic pieces. Given three points $p1 = (x1, y1)$, $p2 = (x2, y2)$, $p3 = (x3, y3)$, calculate the number of mosaic pieces that are fully within the triangle formed by those three points. Note that a mosaic piece is fully within the triangle if its four corners are all located inside the triangle, or on the edge of the triangle.

Take figure 1 for example. Given three points $(3, 3)$, $(10, 2)$ and $(8, 8)$, there are $12$ mosaic pieces located inside the triangle, which are colored in blue.

Figure 1: p10133Figure 1: p10133

Input Format

The input file contains a single line with $6$ integers $x1$, $y1$, $x2$, $y2$, $x3$ and $y3$, representing the three corners of the triangle.

Technical Limitation

  • $p1$, $p2$ and $p3$ will not be on the same line.
  • $-1000 \leq x1, y1, x2, y2, x3, y3 \leq 1000$

Output Format

Output the number of mosaic pieces fully located inside the triangle.

Sample Input 1

3 3 10 2 8 8

Sample Output 1

12

Sample Input 2

0 0 10 0 0 10

Sample Output 2

45

Sample Input 3

20 -2 -16 39 11 -27

Sample Output 3

538

Hint

  • 241. Origin in Quadrilateral
  • The three points may be given in any order.
  • If you use a lot of outer product, be careful with overflow. For example, int val_ab = cross(???), val_bc = cross(???); cause val_ab * val_bc is large than 32-bit integer.

Discussion