### Problem Statement

You are given n distinct straight lines in the plane. The i-th line is specified by two distinct lattice points (x1[i], y1[i]) and (x2[i], y2[i]) that lie on it. These lines divide the plane into regions, and your task is to compute and return the number of finite regions among them. By a finite region we mean a convex polygon bounded by the given lines, with no points belonging to any of the given lines in its interior.

### Definition

 Class: PlaneDivision Method: howManyFiniteParts Parameters: int[], int[], int[], int[] Returns: int Method signature: int howManyFiniteParts(int[] x1, int[] y1, int[] x2, int[] y2) (be sure your method is public)

### Notes

-By a lattice point (x, y) we mean a point on the Cartesian plane with integer coordinates x and y.
-Two points are said to be distinct if either their x-coordinates or y-coordinates differ.

### Constraints

-x1, y1, x2 and y2 will contain the same number of elements.
-x1, y1, x2 and y2 will contain between 1 and 50 elements, inclusive.
-All the elements of x1, y1, x2 and y2 will be between -10000 and 10000, inclusive.
-(x1[i], y1[i]) and (x2[i], y2[i]) will be distinct for all i (i.e., every two points defining a given line will be distinct).
-All the lines defined by (x1[i], y1[i]) and (x2[i], y2[i]) will be distinct.

### Examples

0)

 `{0}` `{0}` `{1}` `{1}`
`Returns: 0`
 A single line divides the plane into two infinite regions.
1)

 `{0, 1, 2}` `{0, 1, -1}` `{1, 2, 0}` `{1, -1, 0}`
`Returns: 1`
 The three lines are the sidelines of a triangle which is the only finite region in this case.
2)

 `{-10000, -9999, 10000, -9999, 0, 500, -500}` `{-9999, 10000, 9999, -10000, 0, 0, 0}` `{-10000, 9999, 10000, 9999, 0, 500, -500}` `{9999, 10000, -9999, -10000, 1, -1, -2}`
`Returns: 4`
 The only finite regions are the 4 big rectangles.
3)

 `{0, 0, 0, 0, 0, 0, 0, 0, 0}` `{0, 0, 0, 0, 0, 0, 0, 0, 0}` `{1, 1, 1, 1, 1, 1, 1, 1, 1}` `{1, 2, 3, 4, 5, 6, 7, 8, 9}`
`Returns: 0`
 All the lines pass through the origin.
4)

 `{-1, -1, -1, -1, 1, 3, -3}` `{-1, -2, 0, 0, 10000, 1, -5}` `{1, 1, 1, -1, 1, -3, 3}` `{1, 0, 2, -10000, 0, -2, 4}`
`Returns: 7`
 1 parallelogramm and 6 triangles are the only finite regions in this case.
5)

 `{-100, -100, -100, -100, -100}` `{-100, -99, -98, -97, -96}` `{100, 100, 100, 100, 100}` `{99, 100, 101, 102, 103}`
`Returns: 0`
 5 parallel lines do not produce any finite regions.
6)

 `{-100, -100, -100, -100, -100, 1}` `{-100, -99, -98, -97, -96, -1}` `{100, 100, 100, 100, 100, -2}` `{99, 100, 101, 102, 103, 2}`
`Returns: 0`
 A configuration of 5 parallel lines and a single line crossing all of them again yields no finite regions.

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7788

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10674&pm=7788

Xixas

#### Testers:

PabloGilberto , brett1479 , Olexiy , ged