J. Image compression

The latest spy gadget is an earring that has a 2 terapixel camera, a 16 core compound graphics processing and CPU unit, 4 TB of overclocked 512-bit GDDRX RAM, and an user-expandable mass storage interface. It can take and transmit photos of the finest quality, whenever your ear itches; and the massive heatsink lends a very fashionable look to the user.

Because of certain legal issues (regarding dubious medical concerns about high-energy electromagnetic radiation near the user's brain), the bandwidth that the earring may utilize during wireless image transmission is extremely small. Until these obsolete regulations are removed, the WSA has to compress the images very severely. They came up with a creative lossy compression format that will keep major features reconstructible, and loses only some unimportant details.

   a random 3d heightmap

The decompressor is already available; your task is to write the compressor. The WSA is looking for an implementation that provides the best image output while staying inside the strict size requirements.

Given a grayscale input png (saved directly from the Intelligent/Imaging Serial CCD), you need to find a suitable compression. The compressed image is described only by a couple of reference points. Each reference point is a pair of coordinates and an intensity. The original image is reproduced by determining the intensity of the missing pixels between reference points using the value of all reference points. The exact method for any given pixel on the output is:

Multiple reference points can not be placed on the same coordinates, all reference points must be within the boundaries of the image.

The maximum number of reference points used to store an image is the sum of SX and SY, the horizontal and vertical dimesions of the image in pixels.


A grayscale png file.


The first line is an integer N, the number of reference points used. The following N lines are reference points in X Y I format where X and Y are the coordinates of the reference point and I is the intensity between 0 (black) and 255 (white).

The top-left pixel of the image is X=0;Y=0.


Scoring is based on the root mean squared error (RMSE):

Valid submissions are rendered to a grayscale image. The render and the input image are compared. The intensity difference of each pixel is squared, then the average of the resulting values is calculated. The square root of the average is the RMSE. This is then compared to the best submission so far. (The eval score in the submission system is trunc(1000000*RMSE)):

  SCORE = 100*(1 - sqrt(1 - BEST/RMSE))

Example input

Example output
(part 1)

14 10 12
4 6 24
0 28 24
11 3 233
17 14 236
13 10 234
30 8 235
31 3 242
28 17 20
14 23 243
10 27 6
2 4 236
20 14 27
20 17 1
13 11 28

Example output
(part 2)

9 22 13
17 9 23
22 14 11
16 6 237
9 29 26
14 4 241
22 11 31
17 30 10
12 9 236
26 8 26
8 19 0
21 23 14
3 23 227
14 2 6
29 11 235
13 23 22
11 28 13