Triangles of a Square

시간 제한1초메모리 제한2048 MB

요약
정사각형의 두 변을 잇는 선분이 하나 주어질 때, 삼각형들로 분할하기 위해 추가로 그어야 하는 선분의 최소 개수를 구한다.
난이도

보통10점 중 4점

유형
기하, 조합론
정답자
아직 제출이 없습니다

문제

Ashley has given Brandon a square of side 20242024. She also has drawn a single line segment that connects two different sides of the square.

Brandon wants to draw some additional line segments such that it is possible to decompose the square into a set of disjoint triangles, where each triangle has sides that are either subsegments of the sides of the square, or subsegments of any drawn line segment.

Compute the minimum number of additional line segments Brandon needs to draw to make this possible.

입력

Imagine that the square is axis-aligned with its bottom-left corner at (0,0)(0, 0) and top-right corner at (2024,2024)(2024, 2024).

Input has a single line with four integers x_1x\_1, y_1y\_1, x_2x\_2, y_2y\_2 (0≤x_1,y_1,x_2,y_2≤20240 ≤ x\_1, y\_1, x\_2, y\_2 ≤ 2024) specifying the coordinates of the end points of the line segment initially drawn by Ashley. One end point is at (x_1,y_1)(x\_1, y\_1) and the other end point is at (x_2,y_2)(x\_2, y\_2).

It is guaranteed the two end points are distinct. Both end points are on sides of the square. If the segment intersects a side of the square, it does so at exactly one point.

출력

Output a single integer, the minimum number of additional line segments Brandon needs to draw.

예제2

  1. 예제 1

    입력
    0 10 10 0
    
    예상 출력
    2
    
  2. 예제 2

    입력
    2024 2024 0 0
    
    예상 출력
    0