Connection Status:
Competition Arena > PowerSupply

PowerSupply

SRM 283 · 2006-01-19 · by gevak

SRM 283 · 2006-01-19 · by gevak · Brute Force, Geometry
Class Name: PowerSupply
Return Type: int
Method Name: maxProfit
Arg Types: (vector<int>, vector<int>, int)
Problem Statement

Problem Statement

You have discovered a region in need of power, and as an enterprising businessperson, you have decided to build a power line there. The region is a cartesian plane, and consumers are represented as points on the plane. Your power line will be a single straight line that is horizontal, vertical, or parallel to any of two diagonals. Each potential consumer will purchase power from your line if and only if the distance between him and your line is less than or equal to D. This distance is measured as the Euclidean distance (the length of the shortest line segment between the point and the line). You would like to maximize your profit by maximizing the number of consumers using your power line.

You are given int[]s x and y containing the coordinates of the consumers. The ith elements of x and y represent the x and y coordinates of the ith consumer. Your are also given an int D, the value described above. Build your power line to maximize the number of consumers that will use it, and return this maximum number.

Notes

  • More than one consumer may be located at the same point.
  • The power line may cross consumer points, in which case those consumers are at a distance of zero from the power line (see example 1).

Constraints

  • x and y will contain between 0 and 50 elements, inclusive.
  • x and y will contain the same number of elements.
  • Each element of x and y will be between -1000000 and 1000000, inclusive.
  • D will be between 0 and 1000000, inclusive.
Examples
0)
{0,3,0,0,0}
{1,2,6,-4,1}
1
Returns: 4
1)
{-1000000,13,1000000}
{0,0,0}
0
Returns: 3

All points are crossed by the line, so all three consumers can connect to the power line even with D equal to 0.

2)
{-5,-2,2,8,-1}
{1,2,1,2,8}
1
Returns: 4
3)
{-5,-5,-2,-2,3}
{-2,-3,4,6,9}
2
Returns: 4
4)
{-12245,-12345,123,123,-17,-17,-17}
{-12345,-12345,735,735,999999,999999,999999}
0
Returns: 3

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

Coding Area

Language: C++17 · define a public class PowerSupply with a public method int maxProfit(vector<int> x, vector<int> y, int D) · 109 test cases · 2 s / 256 MB per case

Submitting as anonymous