SquaredSubsets
SRM 521 · 2011-05-25 · by soul-net
Problem Statement
Given a set of points in the XY plane and an integer n, a subset P of those points is called n-squared if it is not empty and there exists a square of side n in the XY plane with its sides parallel to the axes such that a point from the given set of points is in P if and only if it is contained within the square. A point lying on a side or a vertex of the square is considered to be contained in it.
You will be given n as explained in the input. You will also be given two
Constraints
- n will be between 1 and 100000000 (10^8), inclusive.
- x and y will contain between 1 and 50 elements, inclusive.
- x and y will contain the same number of elements.
- Each element of x and y will be between -100000000 (-10^8) and 100000000 (10^8), inclusive.
- All described points will be different.
5
{-5,0,5}
{0,0,0}
Returns: 5
The following subsets are squared: {(-5,0)}, {(0,0)}, {(5,0)}, {(-5,0),(0,0)}, {(0,0),(5,0)}.
10
{-5,0,5}
{0,0,0}
Returns: 5
The following subsets are squared: {(-5,0)}, {(5,0)}, {(0,0),(5,0)}, {(-5,0),(0,0)}, {(-5,0),(0,0),(5,0)}.
100000000
{-1,-1,-1,0,1,1,1}
{-1,0,1,1,-1,0,1}
Returns: 21
5
{5,3,6,2,1,6,4,4,7,-1,-4,-7,2,-2,0}
{0,-1,8,-5,2,5,-8,8,-6,4,3,2,7,3,5}
Returns: 66
1
{-1,0}
{0,0}
Returns: 3
Submissions are judged against all 98 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SquaredSubsets with a public method long long countSubsets(int n, vector<int> x, vector<int> y) · 98 test cases · 2 s / 256 MB per case