Drone Route Optimization

A drone delivery company wants to optimize its flight routes. Each route is defined by two points in a 2D plane: a starting point ((x_1, y_1)) and an ending point ((x_2, y_2)). Due to overlapping regions, some of these routes may be redundant. Two routes are considered redundant if their segments overlap partially or completely. Your task is to determine the number of unique, non-overlapping routes after eliminating any routes that intersect (even partially) with a previously identified unique route.

For example, given a set of routes, if one route intersects with any already accepted unique route, it is considered redundant and should not be counted as unique. Assume the routes are processed in the order they are given.

The geometric intersection of two segments can be determined based on the orientation of ordered triplets of points. For two segments defined by points (p_1 = (x_1, y_1)), (q_1 = (x_2, y_2)) and (p_2 = (x_3, y_3)), (q_2 = (x_4, y_4)):

• Compute the orientation of each triplet ((p, q, r)) using the formula ( val = (q_y - p_y) * (r_x - q_x) - (q_x - p_x) * (r_y - q_y) ).

• Special cases occur when points are collinear and one point lies on the segment of the other.

Your program should read the number of routes and the route coordinates from the input (from standard input), and output the number of unique, non-overlapping routes (to standard output).

inputFormat

The first line contains an integer (N), representing the number of routes. The second line contains (4 \times N) integers separated by spaces: (x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4, \ldots), where each consecutive four integers represent a route's starting and ending coordinates.

outputFormat

Output a single integer representing the number of unique, non-overlapping routes.## sample

5
0 0 2 2 3 3 5 5 0 0 2 2 6 6 8 8 1 1 4 4

3