TwoLineRegions
TCO19 Round 3A · 2019-04-15 · by lg5293
Problem Statement
This problem has a nonstandard time limit: 3 seconds.
A set of lines in the two-dimensional plane splits the plane into some regions. Given a set of lines L, let two(L) be the number of regions of the plane that are adjacent to exactly two lines in L.
You are given n lines in a 2D plane. The i-th line can be described with the equation a[i]x + b[i]y = c[i]. For your convenience the lines are in a general position. More precisely:
- No line is horizontal or vertical.
- No two lines are parallel.
- No three lines intersect at the same point.
Compute the sum of two(L) where L goes over all subsets of the given n lines. Return the result modulo 10^9 + 7.
Constraints
- n will be between 2 and 1,000, inclusive.
- a,b,c will have exactly n elements each.
- Each element of a,b,c will be between -10,000 and 10,000, inclusive.
- Each element of a,b will be nonzero.
{1,1}
{1,-1}
{0,0}
Returns: 4
Let the two lines be l0 and l1. The value you should find is the sum of two(L) over the following four L: {}, {l0}, {l1}, and {l0,l1}. Obviously, when you have at most one line, there will be zero regions that are adjacent to exactly two lines. The subset that contains both lines produces four such regions. Hence, the answer is 0 + 0 + 0 + 4 = 4.
{1,1,1}
{1,-1,2}
{0,0,-1}
Returns: 15
Each of the three subsets that contain two of the three lines produces 4 good regions. The subset that contains all three lines produces 3 good regions. Thus, the total over all subsets is 3 * 4 + 3 = 15.
{1,-4,-3,3,8,2}
{5,3,-4,7,-2,-10}
{1,-2,-7,1,2,5}
Returns: 190
{-641,827,-531,-804,967,356,873}
{536,897,778,322,-604,-339,253}
{591,-938,837,831,-151,461,694}
Returns: 408
{-4828,-2210,-7007,7070,3467,-1837,6908,5221,7181,2544,
-8805,-7864,-4692,9822,5286,-7007,-452,4005,4523,-1363,
-3702,-1157,5197,-3627,-3653,645,-2331,-4397,-9409,-240}
{-6615,751,-568,9049,-5051,3648,-3729,-941,6227,-1148,848,
853,-19,8846,-3327,-5688,7602,3147,3954,3109,-8913,3595,
6512,6757,3071,600,-9794,-6169,6436,-1560}
{-5459,4853,3715,1840,6991,-3878,6522,1821,-1622,1947,-7613,
-348,-5993,396,4950,-2304,6235,-9146,5392,-1028,3901,-5660,
-6982,-9060,-1945,-4973,-8950,-2569,-1194,7828}
Returns: 412956109
Submissions are judged against all 107 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TwoLineRegions with a public method int count(vector<int> a, vector<int> b, vector<int> c) · 107 test cases · 2 s / 256 MB per case