|Ever wondered why there are so many beheaded zombies walking while beheaded humans are usually laying still? The answer is simple: zombies are more robust due to distributed redundant organs - cutting off only a small part will leave multiple instances of anything vital still connected in the rest of the body. In an ideal world, you would shred zombies to tiny pieces or even grind them to dust. But as in many other fields of life, one can't achieve perfection (there are too many zombies and too few resources for slicing them). However, with some extra cleverness, you can optimize your zombie-slicing-throughput: if you know how zombie organs are distributed, you can minimize the number of cuts needed. As long as each organ will end up separated from all other organs, you are fine, the zombie won't ever come to its horrible pretend life again.|
Having a plane and some points in it, give a set of lines that separate the plane into subplanes so that each subplane can contain at most 1 point. The set should be as small as possible.
Point coordinates are all integers. Lines are given by two different points (with integer coordinates). Lines have a "direction" from their first point to their second point; this is used to determine that when a line intersects an input point, the input point is considered to be on the right side of the line.
Lines can only be horizontal (Y1=Y2), vertical (X1=X2), or diagonal (dX/dY = 1 or -1).
SCORE := round(100 * (1 - sqrt(1 - Smin/S)))Where Smin is the best submission so far.
4 3 1 4 5 6 6 8 4
3 2 8 7 2 8 8 2