Minimum Number of Drones

You are given a fleet of drones used to monitor car movements on roads. Each movement is represented as a line segment with coordinates (x₁, y₁) to (x₂, y₂). A drone can monitor an entire line if the movement is aligned in one of three directions:

• Vertical: if x₁ = x₂,
• Horizontal: if y₁ = y₂,
• Diagonal: if neither of the above is true. Diagonals are classified into two types:
  • Positive slope (\( \Delta x = \Delta y \)) monitored as \(d+\) with invariant \(y_1 - x_1\),
  • Negative slope (otherwise) monitored as \(d-\) with invariant \(y_1 + x_1\).

The task is to determine the minimum number of drones required such that each unique monitored line is covered by one drone. Note that two movements with the same type and corresponding invariant are monitored by the same drone.

inputFormat

The first line of the input contains an integer \(n\) representing the number of movements. Each of the following \(n\) lines contains four integers \(x_1\), \(y_1\), \(x_2\), and \(y_2\) separated by spaces, describing a car movement.

outputFormat

Output a single integer that denotes the minimum number of drones needed to monitor all the movements, i.e. the number of unique monitoring lines.

3
0 0 0 5
1 1 1 4
2 2 2 7

3