#P1448. [NOI1998] 围巾裁剪

[NOI1998] 围巾裁剪

题目描述

裁缝有一块非常珍贵的丝绸围巾。可惜的是,围巾的某些部分已经被蛀虫给咬坏了。裁缝当然不愿意就这么把围巾给丢了,于是,他想把围巾给裁成两块小围巾送给他的两个女儿。自然,两块小围巾的面积之和越大越好。

这块围巾是一个正三角形,三条边被均匀地分成了 NN 段,即这个正三角形被均匀地分成了 N2N^2 个单元,每个单元是一个面积为 11 的正三角形。

如图所示为一个 N=5N=5 的围巾,图中带阴影的单元表示被蛀虫咬坏的部分。
从上往下看,围巾被分成了 NN 行:

  • 第一行有 11 个单元。
  • 第二行有 33 个单元,其中有 22 个是形如 Δ\Delta 的,有 11 个是形如 \nabla 的(这两种三角形我们认为是形状相同的)。
  • 第三行有 55 个单元,其中有 33 个是形如 Δ\Delta 的,有 22 个是形如 \nabla 的……

用坐标 (X,Y)(X,Y) 给每个单元定位,第一行的单元的坐标为 (1,1)(1,1);第二行从左到右的三个单元的坐标依次为 (2,1)(2,1)(2,2)(2,2)(2,3)(2,3);……

围巾的剪裁条件如下:

  1. 裁成的两块小围巾形状与原来的大围巾完全相同,都是正三角形;
  2. 每一块小围巾里都不存在被蛀虫咬坏的部分;
  3. 裁剪时必须沿着单元的边界裁剪;
  4. 要求两块小围巾的面积的总和最大。

图中,最优的裁剪方法已经用粗线画了出来,面积和为 4+9=134+9=13
现在需要你编一个程序来帮助裁缝解决这个问题。

输入格式

输入的第一行为一个整数 N(1N100)N(1\leq N\leq100),表示这块围巾总共被分成了 N2N^2 个单元。第二行为一个整数 M(1MN2)M(1\leq M\leq N^2),表示这块围巾共有 MM 个单元被蛀虫咬坏了。接下来的 MM 行,每一行有两个正整数 XXYY,为这 MM 个被蛀虫咬坏的单元的坐标。

输入文件中同一行相邻两项之间用一个或多个空格隔开。

输出格式

输出文件仅含一个整数,为你所找到的裁出两块小围巾面积总和的最大值。(提示:如果找不到两个符合要求的正三角形,输出 00。)

5
5
3 2
4 1
4 4
5 4
5 2
13

提示

对于 100%100\% 的数据,1N1001\leq N\leq1000MN20\leq M\leq N^2(2023 年 6 月 28 日更正)。