Connection Status:
Competition Arena > PlaneDivision

PlaneDivision

SRM 350 · 2007-05-23 · by Xixas

SRM 350 · 2007-05-23 · by Xixas · Advanced Math, Geometry, Graph Theory
Class Name: PlaneDivision
Return Type: int
Method Name: howManyFiniteParts
Arg Types: (vector<int>, vector<int>, vector<int>, vector<int>)
Problem Statement

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.

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)
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
Returns: 0

13 horizontal lines...

6)
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10000}
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 9999}
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 9999}
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 10000}
Returns: 0

...and a line crossing all of them.

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

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

Submissions are judged against all 146 archived test cases, of which 9 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PlaneDivision with a public method int howManyFiniteParts(vector<int> x1, vector<int> y1, vector<int> x2, vector<int> y2) · 146 test cases · 2 s / 256 MB per case

Submitting as anonymous