HDU 4739

Zhuge Liang's Mines

Description

在三国时期，诸葛亮是最有名也是最聪明的军师。他的死对头是一个叫司马懿的家伙，每次与诸葛亮对战时司马懿都被耍得团团转。但最终，却是司马懿笑到了最后。有一次，诸葛亮派遣马谡防守街亭（街亭是一个非常重要的战略要地，而马谡是诸葛亮好朋友马良的儿子）。主公刘备警告诸葛亮，马谡狂妄自大，不可以派他防守街亭。但最后，诸葛亮没有听从刘备的建议。司马懿最终击败了马谡，并夺取了街亭。诸葛亮不得不挥泪斩马谡，并急忙撤退。为了避免司马懿的追击，诸葛亮在路上放置了许多地雷。他利用八卦阵的思想部署了地雷，使得地雷很难被移除。如果你尝试移除一颗地雷，那么无论你如何做，地雷都会爆炸。但是马谡的儿子背叛了诸葛亮，他找到司马懿，告诉他破解地雷的唯一办法：想要移除地雷，就必须同时移除正方形上的四颗地雷，这样才能成功。司马懿虽然没有诸葛亮聪明，但他也不傻，他尽可能多地移除了地雷。请你计算一下，司马懿移除了多少颗地雷。

Input

输入数据不超过15组。

在每组测试数据中，第一行是一个整数 N ，表示有 N 个地雷。（0 < N ≤ 20）

以下 N 行，描述了 N 颗地雷的坐标。每行包含两个数 X 和 Y ，表示有一颗地雷在坐标( X , Y )处。（0 ≤ X , Y ≤ 100）

输入数据以 N = -1 结尾。

Output

对于每组测试数据，输出司马懿最多可以移除几颗地雷。

Solution

可以先预处理出所有可以组成正方形的地雷，然后用状态压缩 DP 来解决，DP 的时候，只需要枚举状态从 1 到 1 << N 即可。由于 N 比较小，时间复杂度应该是刚刚好。不过这道题目的测试数据不够严格，好像有人用 DFS 就可以过。