PlaneDivision | Topcoder Archive

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}
```
```
{1}
```
```
{1}
```
```
Returns: 0
```
A single line divides the plane into two infinite regions.
```
{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.

{-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.

{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.

{-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.

{-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.

{-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.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.