CF 102697144 - Triangulation Rocks the Nation

The input describes the three vertices of a triangle in the Cartesian plane. Each vertex is given by an integer pair (x, y), and the three vertices may appear in any order. The task is to compute the triangle's area as a decimal value.

codeforcescompetitive-programming

CF 102697144 - Triangulation Rocks the Nation

Rating: -
Tags: -
Solve time: 49s
Verified: yes

Solution

Problem Understanding

The input describes the three vertices of a triangle in the Cartesian plane. Each vertex is given by an integer pair (x, y), and the three vertices may appear in any order. The task is to compute the triangle's area as a decimal value. The problem explicitly describes Heron's formula, so the intended route is to first recover the three side lengths from the coordinates and then substitute them into that formula.

For two points (x1, y1) and (x2, y2), their Euclidean distance is

√((x1 - x2)² + (y1 - y2)²).

After finding the three side lengths A, B, and C, let

S = (A + B + C) / 2.

Heron's formula gives the area as

√(S(S - A)(S - B)(S - C)).

The order of the input points does not matter because every pair of vertices defines one of the three sides. The formula uses all three side lengths symmetrically.

There is no large n here. The input always contains exactly three points, and the published statement does not give a large coordinate-count constraint because there is no variable-size collection to process. Even if the coordinates themselves are very large, the algorithm performs only a constant number of arithmetic operations. There is no possibility of an O(n²) or O(n³) algorithm becoming problematic because there is no growing n in this problem.

The first edge case is a triangle whose area is an integer even though its side lengths are irrational. For example,

0 0
4 0
0 3

has sides 4, 3, and 5, so the correct output is 6.0. A careless implementation that assumes the area must have the same numeric type as the coordinates can incorrectly perform integer division and lose the fractional part in other cases.

A second edge case is an area with a fractional part. For

1 1
5 4
2 8

the correct output is 12.5. Treating all intermediate values as integers cannot represent this result correctly.

A third edge case is a degenerate set of three collinear points. For example,

0 0
1 1
2 2

has area 0.0. Heron's expression is mathematically zero, although floating-point arithmetic can sometimes produce a tiny negative value inside the square root because of rounding. Clamping the expression with max(0.0, expression) makes the implementation robust.

Approaches

A literal brute-force approach could enumerate all six permutations of the three input points, interpret each permutation as an ordering of the triangle's vertices, calculate its three side lengths, and apply Heron's formula. This is correct because every permutation still contains exactly the same three unordered pairs of vertices, so every permutation produces the same three side lengths. It performs six constant-size computations, or 6 × 3 = 18 distance calculations at most, so it is already effectively O(1). There is no meaningful input size at which this brute force becomes too slow.

The useful observation is that the permutation search is unnecessary. Heron's formula depends only on the three side lengths, and those lengths are determined directly by the three unordered pairs of points. We can calculate the distances between points 1 and 2, points 2 and 3, and points 1 and 3 exactly once. The point order supplied by the input is irrelevant.

This is the entire optimization for this problem. Instead of trying possible orderings, calculate the three pairwise distances directly and apply the formula once. The resulting algorithm remains O(1), but it is simpler and avoids six identical calculations.

Approach Time Complexity Space Complexity Verdict
Brute Force O(1), 18 distance calculations at most O(1) Accepted, but unnecessary
Optimal O(1), 3 distance calculations O(1) Accepted

Algorithm Walkthrough

  1. Read the three coordinate pairs and store them as (x, y) points. There are exactly three points, so no data structure beyond three small tuples is required.
  2. Compute the distances between points 1 and 2, points 2 and 3, and points 1 and 3. For each pair, use the Euclidean distance formula. These are precisely the three sides of the triangle, regardless of the order in which the vertices were supplied.
  3. Add the three side lengths and divide by two to obtain the semiperimeter S. Using floating-point division here is necessary because the semiperimeter is not necessarily an integer.
  4. Evaluate S(S - A)(S - B)(S - C). This is the quantity under the square root in Heron's formula.
  5. Take the square root of that quantity and print the result as a decimal number. If floating-point rounding produces a tiny negative value for a degenerate triangle, replace it with zero before taking the square root.

Why it works

The three vertices determine exactly three unordered pairs, and each pair corresponds to one side of the triangle. The algorithm calculates all three pairwise distances, so it obtains exactly the side lengths required by Heron's formula. Heron's formula then computes the area from those three lengths. Since the formula is symmetric in A, B, and C, the original ordering of the vertices cannot affect the result.

Python Solution

import sys
import math

input = sys.stdin.readline

def distance(a, b):
    dx = a[0] - b[0]
    dy = a[1] - b[1]
    return math.hypot(dx, dy)

def solve():
    points = [tuple(map(int, input().split())) for _ in range(3)]

    a = distance(points[0], points[1])
    b = distance(points[1], points[2])
    c = distance(points[0], points[2])

    s = (a + b + c) / 2.0

    value = s * (s - a) * (s - b) * (s - c)
    area = math.sqrt(max(0.0, value))

    print(area)

if __name__ == "__main__":
    solve()

The distance function isolates the coordinate calculation so that the main algorithm directly mirrors the mathematical solution. math.hypot(dx, dy) computes sqrt(dx² + dy²) and is preferable to manually writing the square root expression because it is designed for Euclidean distance calculations.

The three calls use the pairs (0, 1), (1, 2), and (0, 2). These are all three possible pairs of vertices, so no side is missed and no side is counted twice.

The division by 2.0 makes the use of floating-point arithmetic explicit. Python's / operator already performs floating-point division, but the decimal literal makes the intended numerical representation clear.

The max(0.0, value) is a defensive measure for degenerate or nearly degenerate triangles. Mathematically, Heron's expression cannot be negative for a valid triangle, but floating-point rounding can turn a value that should be exactly zero into something like -1e-15. Calling sqrt directly on that value would raise a domain error.

Python integers do not overflow, and the distance calculation is converted to floating point by math.hypot, so there is no separate integer-overflow handling required.

Worked Examples

Sample 1

For the first sample, the points are (1, 1), (5, 4), and (2, 8).

Step Point pair Distance / value
1 (1,1) to (5,4) 5.0
2 (5,4) to (2,8) 5.0
3 (1,1) to (2,8) √50 ≈ 7.0710678119
4 Semiperimeter S 8.5355339059
5 Heron expression 156.25
6 Area 12.5

The three side lengths are approximately 5, 5, and 7.0711. Substituting them into Heron's formula gives exactly 12.5. This demonstrates why the implementation must retain floating-point values throughout the calculation.

Sample 2

For the second sample, the points are (0, 0), (8, 0), and (4, 8).

Step Point pair Distance / value
1 (0,0) to (8,0) 8.0
2 (8,0) to (4,8) √80 ≈ 8.94427191
3 (0,0) to (4,8) √80 ≈ 8.94427191
4 Semiperimeter S 12.94427191
5 Heron expression 1024.0
6 Area 32.0

The result is 32.0. The two equal side lengths also show that the formula does not depend on which vertex was considered first.

Complexity Analysis

Measure Complexity Explanation
Time O(1) Exactly three pairwise distances and one Heron's formula evaluation are performed.
Space O(1) Only three points and a constant number of numeric variables are stored.

The input contains exactly three vertices, so the running time is constant regardless of the coordinate values. The memory usage is also constant. The published problem has a one-second time limit and 256 MB memory limit, and this solution uses only a handful of arithmetic operations and variables.

Test Cases

The official statement provides three samples, so they can be included directly in an assertion-based harness. Because floating-point output can differ slightly between mathematically equivalent calculations, the test helper compares numerical values with a small tolerance.

import sys
import io
import math

def solve():
    input = sys.stdin.readline

    def distance(a, b):
        dx = a[0] - b[0]
        dy = a[1] - b[1]
        return math.hypot(dx, dy)

    points = [tuple(map(int, input().split())) for _ in range(3)]

    a = distance(points[0], points[1])
    b = distance(points[1], points[2])
    c = distance(points[0], points[2])

    s = (a + b + c) / 2.0
    value = s * (s - a) * (s - b) * (s - c)
    area = math.sqrt(max(0.0, value))

    print(area)

def run(inp: str) -> str:
    old_stdin = sys.stdin
    old_stdout = sys.stdout

    sys.stdin = io.StringIO(inp)
    sys.stdout = io.StringIO()

    try:
        solve()
        return sys.stdout.getvalue().strip()
    finally:
        sys.stdin = old_stdin
        sys.stdout = old_stdout

def assert_area(inp: str, expected: float, message: str):
    actual = float(run(inp))
    assert math.isclose(actual, expected, rel_tol=1e-9, abs_tol=1e-9), message

# Provided samples
assert_area(
    "1 1\n5 4\n2 8\n",
    12.5,
    "sample 1"
)

assert_area(
    "0 0\n8 0\n4 8\n",
    32.0,
    "sample 2"
)

assert_area(
    "-1 -3\n2 7\n9 -11\n",
    62.0,
    "sample 3"
)

# Minimum-size meaningful triangle with integer area
assert_area(
    "0 0\n4 0\n0 3\n",
    6.0,
    "right triangle"
)

# All three points are collinear
assert_area(
    "0 0\n1 1\n2 2\n",
    0.0,
    "degenerate triangle"
)

# Fractional area and negative coordinates
assert_area(
    "-1 0\n2 0\n0 1\n",
    1.5,
    "fractional area"
)

# Large coordinates
assert_area(
    "1000000000 1000000000\n1000000004 1000000000\n1000000000 1000000003\n",
    6.0,
    "large coordinates"
)
Test input Expected output What it validates
0 0 / 4 0 / 0 3 6.0 Basic right triangle and exact integer area
0 0 / 1 1 / 2 2 0.0 Collinear points and the square-root boundary
-1 0 / 2 0 / 0 1 1.5 Fractional result and negative coordinates
1000000000 1000000000 / 1000000004 1000000000 / 1000000000 1000000003 6.0 Large coordinate values

Edge Cases

For the fractional-area case

-1 0
2 0
0 1

the side lengths are 3, √2, and √2. The semiperimeter is approximately 2.9142, and Heron's formula gives 1.5. The algorithm keeps the semiperimeter and all four factors as floating-point values, so no fractional information is lost.

For the collinear case

0 0
1 1
2 2

the side lengths are √2, √2, and 2√2. The semiperimeter is 2√2, making the factor S - C mathematically zero. The intended area is 0.0. Because floating-point calculations may produce a tiny negative value instead, max(0.0, value) guarantees that the square root receives a valid nonnegative argument.

For the large-coordinate case

1000000000 1000000000
1000000004 1000000000
1000000000 1000000003

the translated shape is a 4 × 3 right triangle, whose area is 6.0. The algorithm works with coordinate differences before computing distances, so the large absolute coordinate values do not change the geometry. Python's arbitrary-precision integers also prevent integer overflow while those differences are formed.

The arbitrary input order is handled automatically because the algorithm computes all three possible pairs. For example, swapping the first and third points changes which pair is called a or c, but Heron's formula treats the three side lengths symmetrically, so the final area remains unchanged.