#今天要来点数学吗？# #算法[超话]#

2016年国际信息学奥林匹克竞赛（IOI 2016） 有一道题目名为 外星人"Aliens"。

当年全球300多名高中精英学生，仅有一人满分。

外星人一题因此名声大噪，以至于解题方法被称为Aliens Trick“外星人技巧”。它结合了拉格朗日松弛法和二分查找法，可以显著降低#动态规划# 复杂度。

但“外星人技巧”并非什么新鲜事。早在这场比赛的四年前（2012年）就有人发现了它。

2012年，年仅17岁的王钦石发表了相关论文。在中国，外星人技巧早已被称之为“WQS二分查找”，以王钦石的名字首字母命名。

他是我老乡，在高中阶段，就是黑龙江省过去几十年里取得最好成绩的竞赛生——距离国家队一步之遥。

——————————
翻译一下题目

人类的卫星刚刚在一个遥远的行星上发现了一个外星文明。我们已经获取了该行星上一块正方形区域的低分辨率照片。

照片显示了许多智慧生命的迹象。我们的专家在照片中识别出了n个兴趣点。这些点被编号为0到n-1。

现在我们想要拍摄包含所有这n个点的高分辨率照片。卫星将低分辨率照片的区域划分为了一个m×m的单位正方形网格。网格的行和列都从0到m-1 连续编号（分别从上到下、从左到右）。

我们使用 (s, t)来表示位于第s行第t列的单元格。编号为i的点位于单元格 (r_i, c_i) 中。

每个单元格可能包含任意数量的兴趣点。卫星处于一个稳定的轨道上，该轨道正好经过网格的主对角线上方。

主对角线是连接网格左上角和右下角的线段。卫星可以拍摄满足以下约束条件的任意区域的高分辨率照片：拍摄区域的形状必须是正方形。该正方形的两个相对的顶点必须都位于网格的主对角线上。

网格的每个单元格要么完全在拍摄区域内，要么完全在拍摄区域外。卫星最多能拍摄 k张高分辨率照片。一旦卫星完成拍摄，它会将每个被拍摄到的单元格的高分辨率照片传回我们的基地（无论该单元格是否包含兴趣点）。

每个被拍摄单元格的数据只会被传输一次，即使该单元格被多次拍摄（即有重叠区域）。因此，我们必须选择最多k个正方形拍摄区域，并确保：每个包含至少一个兴趣点的单元格都至少被拍摄一次。被拍摄至少一次的单元格总数被最小化。

你的任务是找出被拍摄单元格的最小可能总数。

实现细节：你需要实现以下函数（方法）：

int64 take_photos(int n, int m, int k, int[] r, int[] c)

n：兴趣点的数量。
m：网格的行数（也是列数）。
k：卫星最多能拍摄的照片数量。
r 和c：两个长度为n的数组，描述包含兴趣点的网格单元格的坐标。

对于0＜i＜n-1，第i个兴趣点位于单元格(r[i], c[i])。该函数应返回被拍摄至少一次的单元格的最小可能总数（前提是照片必须覆盖所有的兴趣点）。

或者阅读官方原题 http://t.cn/AXI5pXG6

ps 有一个有趣的事情，

有位正在备战信息学竞赛的外国少年，用4个小时学习WQS二分查找，并在网上分享了学习经验。

王钦石的英语拼写Qinshi Wang。

有个不知道是哪国人的网友问道“ is his name really 秦始皇”（或许是浏览器翻译的锅）

那个少年回复：yes。

我赶紧在下面纠正，nonono，his name is written in Chinese as “王钦石”（你信他是秦始皇，还是信我……）[笑cry]

此外，如果不是盗用名字的话，现在王钦石加盟了天津某教培机构，从事AI赋能的儿童编程教学。