You are given N points on a two-dimensional plane. You have to enclose these points with at most M circles so that each point is inside of at least one circle. Your task is to minimize the sum of areas of the circles you use.
Your code should implement one method placeCircles. ints pointX and pointY give you the coordinates of the points on the plane, and M is the maximal number of circles you can use.
You must return the list of the circles you'll use to enclose these points. Each element of your return describes one circle and should be formatted as "CENTERX CENTERY RADIUS" (quotes for clarity only). CENTERX and CENTERY specify x- and y-coordinates of the circle's center, and RADIUS specifies its radius. RADIUS must be strictly greater than 0.1. All values are double precision.
Your score for an individual test case will be the sum of the areas of the circles you used. Note that the score is NOT equal to the area on the plane covered with the circles; if the returned circles overlap, the area of the overlap is counted for each overlapping circle. If at least one of the given points is outside of all circles, your score for this test case will be zero. An invalid return of any kind will result in zero absolute score for that test case.
Your overall score will be the sum over all test cases of max(0, 400000 - AREA) / 1000, where AREA is the area you used.
Test Case Generation
The number of points N is chosen between 50 and 1000, inclusive.
The maximal number of circles M is chosen between 10 and max(10, floor(N / 10)), inclusive.
x- and y-coordinates of each point are chosen between 0 and 511, inclusive.
You will have the opportunity to submit four test cases during the first week of the contest. Of the four, one will be selected at random for provisional testing, while the others will be used for final testing. After the first week, the submitted test cases will be locked. Your code should implement a method generateTestCase that takes one int argument and returns a int that contains the information about the test case that you want to submit. The first element must contain M. The second element must contain N. The next N elements should contain the values for pointX, following that another N elements that contain the values for pointY. This solution will be called four times on some tests -- you should not count on it being called every time. The test case will be validated and only valid test cases will be accepted.
A visualizer is available for offline testing.