裁缝有一块非常珍贵的丝绸围巾。可惜的是，围巾的某些部分已经被蛀虫给咬坏了。裁缝当然不愿意就这么把围巾给丢了，于是，他想把围巾给裁成两块小围巾送给他的两个女儿。自然，两块小围巾的面积之和越大越好。
这块围巾是一个正三角形，三条边被均匀地分成了N段，即这个正三角形被均匀地分成了N2个单元，每个单元是一个面积为1的正三角形。图一所示为一个N=5的围巾，图中带阴影的单元表示被蛀虫咬坏的部分。从上往下看，围巾被分成了N行，{dy}行有1个单元，第二行有3个单元，其中有2个是形如D 的，有1个是形如Ñ 的（这两种三角形我们认为是形状相同的）。第三行有5个，其中有3个是形如D 的，有2个是形如Ñ 的…… 。用坐标（X,Y）给每个单元定位，{dy}行的单元的坐标为（1,1）；第二行从左到右的三个单元的坐标依次为（2,1）、（2,2）、（2,3）；…。
围巾的剪裁条件如下：
1.裁成的两块小围巾形状与原来的大围巾xx相同，都是正三角形。
2.每一块小围巾里都不存在被蛀虫咬坏的部分。
3.裁剪时必须沿着单元的边界裁剪。
4.要求两块小围巾的面积的总和{zd0}。
图一中，{zy}的裁剪方法已经用粗线画了出来，面积和为4+9=13。
现在需要你编一个程序来帮助裁缝解决这个问题。
输入
输入文件{dy}行为一个整数N（1£ N£ 100），表示这块围巾总共被分成了N2个单元。第二行为一个整数M（0£ M£ N2-2），表示这块围巾共有M个单元被蛀虫咬坏了。接下的M行，每一行有两个正整数X和Y，为这M个被蛀虫咬坏的单元的坐标。
输入文件中同一行相邻两项之间用一个或多个空格隔开。
输出
输出文件仅含一个整数，为你所找到的裁出两块小围巾面积总和的{zd0}值。
样例输入
5
5
3 2
4 1
4 4
5 4
5 2
样例输出
13
var
n,m,ans:longint;
map,keep:array[0..110,0..210] of boolean;
f:array[0..110,0..210] of longint;
procedure init;
begin
assign(input,'cut.in');
assign(output,'cut.out');
reset(input);
rewrite(output);
end;
procedure terminate;
begin
close(input);
close(output);
end;
procedure readdata;
var
x,y:longint;
var
i:longint;
begin
fillchar(map,sizeof(map),1);
readln(n);readln(m);
for i:=1 to m do
begin
readln(x,y);
map[x,y]:=false;
end;
keep:=map;
end;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
procedure work;
var
max1,max2,i,j,k:longint;
begin
fillchar(f,sizeof(f),0);
for i:=1 to 2*n-1 do
f[n,i]:=ord(map[n,i]);
for i:=n-1 downto 1 do
for j:=1 to 2*i-1 do
begin
if (j and 1=0) or not map[i,j] then continue;
f[i,j]:=1;
if map[i+1,j+1] then f[i,j]:=min(f[i+1,j],f[i+1,j+2])+1;
end;
f[2,2]:=1;
for i:=3 to n do
for j:=1 to 2*i-1 do
begin
if (j and 1=1) or not map[i,j] then continue;
f[i,j]:=1;
if map[i-1,j-1] then f[i,j]:=min(f[i-1,j],f[i-1,j-2])+1;
end;
for i:=1 to n-1 do//枚举分割线的时候只能到n-1，因为要保证至少切出两块，到n的话就只有一块了。
begin
max1:=0;max2:=0;//这两个容器每次都要清零
for k:=1 to i do
for j:=1 to 2*k-1 do
begin
if j and 1=1 then
begin
if max1<min(f[k,j],i-k+1) then max1:=min(f[k,j],i-k+1)
end
else
if max1<f[k,j] then max1:=f[k,j];
end;
for k:=i+1 to n do
for j:=1 to 2*k-1 do
begin
if j and 1=1 then
begin
if max2<f[k,j] then max2:=f[k,j]
end
else
if max2<min(f[k,j],k-i) then max2:=min(f[k,j],k-i);
end;
if max1*max1+max2*max2>ans then ans:=max1*max1+max2*max2;
end;
end;
procedure change1;
var
i,j,a,b:longint;
begin
for i:=n downto 1 do
begin
a:=n-i+1;b:=2*a;
for j:=1 to 2*i-1 do
begin
if j and 1=1 then dec(b) else
begin
inc(a);
inc(b);
end;
map[i,j]:=keep[a,b];
end;
end;
end;
procedure change2;
var
i,j,a,b:longint;
begin
for i:=n downto 1 do
begin
a:=n+1;b:=2*i;
for j:=1 to 2*i-1 do
begin
if j and 1=0 then dec(b) else
begin
dec(a);
dec(b);
end;
map[i,j]:=keep[a,b];
end;
end;
end;//两个旋转模块一定要仔细地写
procedure main;
begin
ans:=-100;
work;
change1;
work;
change2;
work;
writeln(ans);
end;
begin
init;
readdata;
main;
terminate;
end.
哎……两个小时，终于做出来了……类似的题还有盖房子之类的，反正比较简单，可是我菜……
解题报告：
第四题：围巾裁剪（Cut）
设gd[i,j]表示以坐标i,j为顶点的{zd0}三角形的边长。需要考虑正反三角两种情况，这里以正三角为例。
gd[i,j]=min{gd[i+1,j],gd[i+1,j+2]}+1 (i+1,j+1)完好
1 (i+1,j+1)损坏但(i,j)完好
0 (i,j)损坏
枚举分界线（3种方向），分界线把大三角形围巾分成一个小三角形围巾和一个梯形围巾，由gd+考虑边界可以求出每个小图形中的{zd0}完好围巾。
其中{zd0}的为所求。
时间复杂度O(n3)。
至于枚举三种方向的分界线我用的是旋转的方式，每次把图逆时针旋转一次，一共旋转三次。
还有一个以前没有注意过的问题——每个else默认和最近的if then 连在一起，所以需要的话要加begin，end。
