Strictly Inscribed Similar Triangles

Time limit1sMemory limit128 MB

Summary
For each triangle and angle theta, count how many strictly inscribed triangles similar in order to the given triangle exist with a chosen edge at that angle.
Level

Hard8 of 10

Topics
Geometry, Math, Brute force, Implementation
Solved
No attempts yet

Problem

Two triangles ABCABC and XYZXYZ are similar if their corresponding sides are proportional (equivalently, if their corresponding angles are equal). We say that ABCABC and XYZXYZ are similar in order if AA corresponds to XX, BB corresponds to YY, and CC corresponds to ZZ. That is,

∣AB∣∣XY∣=∣BC∣∣YZ∣=∣AC∣∣XZ∣,\frac{|AB|}{|XY|} = \frac{|BC|}{|YZ|} = \frac{|AC|}{|XZ|},

where ∣MN∣|MN| denotes the length of the segment from MM to NN.

Triangle XYZXYZ is strictly inscribed in triangle ABCABC if each vertex of XYZXYZ lies in the interior (not at a vertex) of a different edge of ABCABC. This means no edge of XYZXYZ can be contained in an edge of ABCABC. If XYZXYZ is similar in order to ABCABC and strictly inscribed in ABCABC, we call XYZXYZ a strictly inscribed similar triangle of ABCABC.

If the line through XX and YY makes an angle θ\theta with the line through AA and BB, there are four possible orientations, illustrated below: XX and YY may be at either end of the segment, and the third vertex ZZ may be on either side of the line. In the figure, the line through XX and YY makes an angle of 30∘30^\circ with the line through AA and BB.

Depending on the shape of the outer triangle ABCABC and the angle θ\theta between the line through XX and YY and the line through AA and BB, there may be 0, 1, 2, 3, or 4 strictly inscribed similar triangles of ABCABC with angle θ\theta.

Given the vertices of triangle ABCABC and an angle θ\theta, determine how many strictly inscribed similar triangles of ABCABC exist for which the line through XX and YY makes an angle θ\theta with the line through AA and BB.

Input

The first line contains a positive integer nn, the number of triangle datasets that follow. Each dataset consists of four lines: the first line has the xx and yy coordinates of vertex AA, the second line has the xx and yy coordinates of vertex BB, the third line has the xx and yy coordinates of vertex CC, and the fourth line has the angle θ\theta (in degrees) between the line through XX and YY and the line through AA and BB.

Output

For each dataset, output a single line containing one integer: the number of strictly inscribed similar triangles of ABCABC for which the line through XX and YY makes an angle θ\theta with the line through AA and BB.

Examples7

  1. Example 1

    Input
    2
    0 0
    21 0
    14 6
    30
    0 0
    21 0
    14 6
    50
    
    Expected output
    2
    1
    
  2. Example 2

    Input
    1
    0 0
    21 0
    14 6
    15
    
    Expected output
    4
    
  3. Example 3

    Input
    1
    0 0
    21 0
    14 6
    80
    
    Expected output
    0
    
  4. Example 4

    Input
    1
    0 0
    21 0
    14 6
    150
    
    Expected output
    3
    
  5. Example 5

    Input
    1
    0 0
    21 0
    14 6
    55
    
    Expected output
    1
    
  6. Example 6

    Input
    1
    0 0
    10 0
    3 8
    40
    
    Expected output
    4
    
  7. Example 7

    Input
    5
    0 0
    21 0
    14 6
    15
    0 0
    21 0
    14 6
    35
    0 0
    21 0
    14 6
    55
    0 0
    21 0
    14 6
    80
    0 0
    21 0
    14 6
    150
    
    Expected output
    4
    2
    1
    0
    3