CF 102697072 - Tri-Angle

We are given exactly three points in the plane, representing the vertices of an isosceles triangle. The three input lines may appear in any order.

codeforcescompetitive-programming

CF 102697072 - Tri-Angle

Rating: -
Tags: -
Solve time: 1m
Verified: yes

Solution

Problem Understanding

We are given exactly three points in the plane, representing the vertices of an isosceles triangle. The three input lines may appear in any order. The task is to determine the direction in which the triangle points, meaning the direction of its symmetry axis from the midpoint of the equal base toward the opposite vertex.

For example, with points (-1, 0), (0, 1), and (-2, 2), the equal sides meet at (-2, 2). The midpoint of the other two points is (-0.5, 0.5), so the symmetry axis points along ( -1.5, 1.5 ), which has direction 135 degrees from the positive x-axis. The required answer is consequently 135.0.

The coordinates are floating point values, and the statement does not give a meaningful large n or repeated test-case parameter. There are always exactly three points, so even an approach that examines every possible choice of apex performs only a constant number of arithmetic operations. There is no possibility of an O(n^2) or similar asymptotic issue here. The main difficulty is geometric identification of the apex and correct handling of the angle returned by atan2.

The first edge case is a triangle whose symmetry axis points exactly along the positive x-axis. For example,

0 02 01 1

The apex is (1, 1), the base midpoint is (1, 0), and the direction is (0, 1), so the correct output is 90.0. A careless implementation that measures the angle of the vector from the apex toward the base would output 270.0, reversing the required direction.

A second edge case occurs when the direction has a negative y-component. For example,

0 02 01 -1

The direction is downward, so the mathematical angle is -90 degrees when returned directly by atan2. The required representation is between 0 and 360, so the correct output is 270.0. Forgetting to normalize negative angles produces the wrong result.

A third edge case is when the input points are presented in an arbitrary order. For example,

-2 2-1 00 1

The answer is still 135.0. An implementation that assumes the first point is the apex will accidentally use the wrong symmetry axis.

A degenerate case deserves separate attention. An equilateral triangle has three possible choices of apex because all three sides are equal, so it has no unique pointing direction. The problem's intended isosceles-triangle input must consequently provide a unique apex. The algorithm below relies on that property.

Approaches

The direct approach is to try each of the three points as the possible apex. For a chosen point A, the other two points B and C must be equally distant from A if A is the apex of the isosceles triangle. We can compare the squared distances AB² and AC², avoiding square roots entirely. Once the correct apex is found, the midpoint of BC gives a point on the symmetry axis, and the vector from that midpoint toward A gives the requested direction.

This brute-force approach is already constant time because there are only three possible apexes. In the worst case, we inspect all three candidates and perform two squared-distance calculations for each, for at most six distance comparisons plus a constant amount of geometry. There is no practical performance problem.

The useful geometric observation is that the apex is characterized entirely by equal distances to the other two vertices. We do not need to calculate any triangle angles or determine which side is the base first. Once the equal-side endpoint is known, the line through that endpoint and the midpoint of the opposite side is exactly the triangle's symmetry axis.

A slightly cleaner formulation is to compute all three squared side lengths. In a non-equilateral isosceles triangle, two of them are equal, and the remaining side is the base. If AB = AC, then A is the apex. If AB = BC, then B is the apex. Otherwise C is the apex. With floating point input, comparisons should use a small relative tolerance rather than requiring exact binary equality.

The brute-force and geometric approaches have the same asymptotic complexity because the input itself contains only three points. The second formulation is preferable because it makes the geometric invariant explicit and avoids any unnecessary search over permutations.

Approach Time Complexity Space Complexity Verdict
Brute Force O(1) O(1) Accepted
Equal-side identification O(1) O(1) Accepted

Algorithm Walkthrough

  1. Read the three points A, B, and C. Their order does not carry any geometric meaning, so we must determine the apex ourselves.
  2. Compute the three squared side lengths AB², AC², and BC². Squared distances are sufficient because equality of positive distances is equivalent to equality of their squares, and avoiding square roots gives simpler and more stable arithmetic.
  3. Determine which point is the apex. If AB² and AC² are equal, then A is equidistant from the other two points and is the apex. Otherwise, if AB² and BC² are equal, B is the apex. The remaining case makes C the apex.
  4. Let A be the identified apex and B, C be the base endpoints. Compute the midpoint of the base as

M = ((Bx + Cx) / 2, (By + Cy) / 2).

The symmetry axis passes through the apex and this midpoint because an isosceles triangle is symmetric around the perpendicular bisector of its base. 5. Construct the direction vector from the base midpoint toward the apex:

v = A - M.

The direction must point toward the apex, not away from it, because the problem asks which way the triangle is pointing. 6. Use atan2(vy, vx) to obtain the signed angle from the positive x-axis. Convert it from radians to degrees. 7. If the angle is negative, add 360. The resulting value lies in the required [0, 360) range.

Why it works

The apex of an isosceles triangle is exactly the vertex connected to the other two vertices by equal-length sides. Thus comparing the three squared side lengths uniquely identifies the apex for every valid non-equilateral input. Once the apex and base are known, the midpoint of the base lies on the perpendicular bisector of the base, which is also the triangle's symmetry axis. The vector from that midpoint to the apex consequently has exactly the requested direction. Finally, atan2 measures that vector relative to the positive x-axis, and adding 360 to a negative result converts the signed representation into the required positive representation without changing its direction.

Python Solution

Pythonimport sysimport math
input = sys.stdin.readline

def equal(a, b):    return math.isclose(a, b, rel_tol=1e-9, abs_tol=1e-9)

def solve():    points = [tuple(map(float, input().split())) for _ in range(3)]    A, B, C = points
    def dist2(P, Q):        dx = P[0] - Q[0]        dy = P[1] - Q[1]        return dx * dx + dy * dy
    ab = dist2(A, B)    ac = dist2(A, C)    bc = dist2(B, C)
    if equal(ab, ac):        apex = A        base1 = B        base2 = C    elif equal(ab, bc):        apex = B        base1 = A        base2 = C    else:        apex = C        base1 = A        base2 = B
    mid_x = (base1[0] + base2[0]) / 2.0    mid_y = (base1[1] + base2[1]) / 2.0
    vx = apex[0] - mid_x    vy = apex[1] - mid_y
    angle = math.degrees(math.atan2(vy, vx))
    if angle < 0:        angle += 360.0
    print(angle)

if __name__ == "__main__":    solve()

The dist2 function computes squared Euclidean distance. Since only equality matters when identifying the equal sides, taking square roots would add work without adding information.

The equal helper uses math.isclose because the coordinates are read as floating point values. Direct comparisons such as ab == ac can fail when mathematically equal quantities acquire slightly different floating point representations.

The three comparisons encode the three possible apexes. If AB = AC, the two sides incident to A are equal. If AB = BC, the two equal sides meet at B. If neither condition holds, the equal sides must meet at C.

The midpoint is calculated before constructing the direction vector. The subtraction order is deliberate: apex - midpoint points from the center of the base toward the tip of the triangle. Reversing the subtraction would rotate the answer by exactly 180 degrees.

atan2 handles all four quadrants, including vertical vectors where an ordinary atan(y / x) would divide by zero. Its result is in radians and in the interval [-180, 180] after conversion to degrees. Adding 360 only when the value is negative maps it into the required positive range.

Python integers would not overflow, but the coordinates are floating point values anyway, so all geometric calculations naturally use Python's floating point representation.

Worked Examples

The statement provides one sample, and a second example can be constructed to exercise angle normalization.

Sample 1

Input:

-2 20 1-1 0

The three squared side lengths are:

Step AB² AC² BC² Apex
Read points 5 5 2 A = (-2, 2)

Here the first point is equidistant from the other two, so it is the apex. The base midpoint is (-0.5, 0.5), giving the direction vector (-1.5, 1.5).

Apex Base midpoint vx vy Angle
(-2, 2) (-0.5, 0.5) -1.5 1.5 135.0

The vector lies in the second quadrant, so atan2 directly produces 135 degrees. The output is 135.0, matching the sample.

Example 2

Input:

0 02 01 -1

The squared lengths are 4, 2, and 2. The equal sides meet at (1, -1), so that point is the apex.

Step AB² AC² BC² Apex
Read points 4 2 2 C = (1, -1)

The midpoint of the base is (1, 0), so the symmetry-axis vector is (0, -1).

Apex Base midpoint vx vy Raw angle Normalized
(1, -1) (1, 0) 0 -1 -90.0 270.0

This example demonstrates why the final normalization is necessary. The geometric direction is downward, which is 270 degrees in the required counterclockwise convention.

Complexity Analysis

Measure Complexity Explanation
Time O(1) Exactly three points are processed, so only a fixed number of arithmetic operations are performed.
Space O(1) Only the three points, side lengths, and a few scalar variables are stored.

The problem contains a fixed number of points, so the algorithm is effectively instantaneous regardless of coordinate magnitude. The memory usage is also constant and far below the stated memory limit of 256 MB.

Test Cases

Pythonimport sysimport ioimport math

def solve_input(inp: str) -> str:    data = inp.strip().splitlines()    points = [tuple(map(float, line.split())) for line in data[:3]]
    def dist2(a, b):        dx = a[0] - b[0]        dy = a[1] - b[1]        return dx * dx + dy * dy
    def equal(a, b):        return math.isclose(a, b, rel_tol=1e-9, abs_tol=1e-9)
    A, B, C = points    ab = dist2(A, B)    ac = dist2(A, C)    bc = dist2(B, C)
    if equal(ab, ac):        apex, p, q = A, B, C    elif equal(ab, bc):        apex, p, q = B, A, C    else:        apex, p, q = C, A, B
    mx = (p[0] + q[0]) / 2    my = (p[1] + q[1]) / 2
    angle = math.degrees(math.atan2(apex[1] - my, apex[0] - mx))    if angle < 0:        angle += 360
    return f"{angle}\n"

def run(inp: str) -> str:    return solve_input(inp)

# Provided sampleassert run("""-2 20 1-1 0""") == "135.0\n", "sample 1"
# Minimum-size coordinate pattern, pointing rightassert run("""0 00 21 1""") == "0.0\n", "horizontal direction"
# Negative-angle normalizationassert run("""0 02 01 -1""") == "270.0\n", "downward direction"
# Arbitrary input orderassert run("""-1 0-2 20 1""") == "135.0\n", "unordered vertices"
# Vertical directionassert run("""-1 01 00 2""") == "90.0\n", "vertical direction"
# Symmetry axis pointing leftassert run("""0 00 2-1 1""") == "180.0\n", "left direction"
Test input Expected output What it validates
0 0 / 0 2 / 1 1 0.0 Exact 0 degree boundary and horizontal axis
0 0 / 2 0 / 1 -1 270.0 Negative atan2 result and normalization
-1 0 / -2 2 / 0 1 135.0 Vertices arriving in a different order
-1 0 / 1 0 / 0 2 90.0 Vertical symmetry axis
0 0 / 0 2 / -1 1 180.0 Exact 180 degree boundary

Edge Cases

For the horizontal zero-degree case,

0 00 21 1

the equal sides meet at (1, 1). The base midpoint is (0, 1), so the direction vector is (1, 0). atan2(0, 1) returns 0, and the algorithm prints 0.0. There is no special case needed for zero itself because the normalization only changes negative angles.

For the downward direction,

0 02 01 -1

the equal sides meet at (1, -1). The base midpoint is (1, 0), producing (0, -1). atan2(-1, 0) gives -90 degrees. The algorithm adds 360, producing 270.0. This is the boundary case most likely to expose an implementation that forgets the required positive angle range.

For the arbitrary ordering case,

-1 0-2 20 1

the equal sides still meet at (-2, 2), even though that point is in the middle of the input. The squared distances from (-2, 2) to the other two points are both 5, so the second comparison identifies it as the apex. The resulting vector is (-1.5, 1.5), giving 135.0.

For the vertical direction,

-1 01 00 2

the base midpoint is (0, 0) and the apex is (0, 2). The direction vector is (0, 2), so atan2 returns 90.0. This also demonstrates why atan2 is preferable to manually computing atan(vy / vx), since the x-component is exactly zero.

For the left-facing direction,

0 00 2-1 1

the base midpoint is (0, 1) and the apex is (-1, 1). The direction vector is (-1, 0), giving exactly 180.0. The algorithm leaves this value unchanged because it is already inside the required range.