问题 2602 --雷神领域

2602: 雷神领域

题目描述

  Lwins_7k+ (GYZ),Synophia大陆首屈一指的天才魔法师,创造了一个新魔法:雷神领域。
这个魔法会首先在地面上形成正方网格魔法阵列,然后在某些位置召唤雷电轴标。注意:一个位置只能有一个雷电轴标存在。雷电轴标总出现在正方网格魔法阵列的顶点处,所以我们可以用一个有序整数对(x_i,y_i)标记它的位置。
然后,如果存在三个雷电轴标A,B,C满足:x_A=x_B, y_A=y_C,则该魔法会立即召唤一个位置在(x_C,y_B)的雷电轴标,如此往复直至不存在满足条件的雷电轴标组为止。
最后,Lwins_7k+将选择一条正方网格魔法阵列上的路径并使用自然力激活它们,这时候雷神领域的魔法强度就被定义为路径上的雷电轴标所占用的行数/列数中的较小值。但是由于Lwins_7k+才刚创造这个魔法,如果选择的路径中出现U形或往返子路径,那么会给施展魔法的魔法师带来一定危险性。所以选择的路径不应该包含U形子路径或往返子路径。(类似 |__ __ __| 这样的广义U形路径也不行)
由于自然力必须从魔法师的体内调和,所以路径的起点应该是魔法师所站的位置,即正方网格魔法阵列的左下角(0,0)点。
现在他想要询问你——以扫地为生来隐藏自己真实身份的大陆有史以来最伟大的式神制造师Lwins_***,他所能释放的雷神领域的最高魔法强度。当然,路径由你来为他选择。虽然如此,作为一个魔法天才,其实他只关心最高魔法强度而已。

输入

输入文件field.in第一行包含一个正整数N,表示接下来的数据个数。
接下来N行,每行包含两个正整数x_i,y_i,表示(x_i,y_i)处存在一个雷电轴标。

输出

输出文件field.out仅包含一行,为可能的最高魔法强度。

样例输入输出

输入#1 复制
7
1 1
1 1
1 1
1 2
1 3
2 2
3 1
输出#1 复制
3

提示

【数据规模】
对于30%的数据:N<=10, 0<x_i,y_i<=5。
对于80%的数据:0<x_i,y_i<=2000。
对于100%的数据:N<=15000, 0<x_i,y_i<=5000。

序号 标题 作者 发表时间 费用 订购数 操作