Minimum Cuts for Intrusion‐Detection Wires

The Intrusion and Crime Prevention Company (ICPC) has designed a security system for a door equipped with sensors located on its four sides. Every wire connects a pair of sensors on the door’s boundary (so that each wire is a chord of the convex door). When the door is opened, any wire that is still intact would trigger an alarm because its sensor pair would be connected. However, an intruder may cut some wires beforehand. To assess the security of the system, you are to compute the minimum number of straight‐line cuts that together intersect (that is, "stab") every wire.

A cut is a straight line segment drawn on the door’s surface. You may choose its position and orientation arbitrarily, as long as its infinite extension would intersect every wire that it is meant to cut. (Note that the wire is the straight segment connecting its two sensor endpoints on the door boundary.)

A key observation is that because the door is convex and every wire is a chord of the door, if a single cut exists that intersects every wire then one may use that cut – otherwise it can be shown that two cuts always suffice to intersect all wires. (You do not need to prove this fact.)

Given the positions of the two endpoints for each wire (each endpoint is guaranteed to lie on the door’s boundary), determine whether one cut is enough. If so, output 1; otherwise, output 2.

Intersection Criterion. Given an infinite line ℓ defined by two distinct points A and B and a segment s defined by endpoints P and Q, ℓ is said to intersect s if and only if P and Q lie in opposite closed half‐planes with respect to ℓ. Equivalently, if we define the cross product

[ \operatorname{cross}(A,B,X) = (B_x - A_x) \cdot (X_y - A_y) - (B_y - A_y) \cdot (X_x - A_x), ]

then ℓ and s intersect if and only if

[ \operatorname{cross}(A,B,P) \times \operatorname{cross}(A,B,Q) \le 0. ]

You may assume that no two sensor positions coincide and that each wire has positive length.

inputFormat

The input consists of one test case. The first line contains an integer n (1 ≤ n ≤ 50) giving the number of wires. Each of the next n lines contains four integers x1 y1 x2 y2 describing the coordinates of the two endpoints of a wire. All endpoints lie on the boundary of the door, which is a convex polygon (in fact, a rectangle). For example, a point is on the boundary if either its x-coordinate equals 0 or a given width, or its y-coordinate equals 0 or a given height. (The exact dimensions are not needed as the wires always lie inside the door.)

You may assume that 0 ≤ x1,x2,y1,y2 ≤ 10, and that no wire degenerates to a point.

outputFormat

Output a single integer: 1 if there exists a straight‐line cut that intersects every wire, and 2 otherwise.

sample

1
0 0 10 0

1