网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
第二试-围巾裁剪
成绩 | 0 | 开启时间 | 2013年01月22日 星期二 13:45 |
折扣 | 0.8 | 折扣时间 | 2013年01月22日 星期二 13:45 |
允许迟交 | 是 | 关闭时间 | 2013年01月22日 星期二 13:45 |
输入文件 | scarfcut.in | 输出文件 | scarfcut.out |
裁缝有一块非常珍贵的丝绸围巾。可惜的是,围巾的某些部分已经被蛀虫给咬坏了。裁缝当然不愿意就这么把围巾给丢了,于是,他想把围巾给裁成两块小围巾送给他的两个女儿。自然,两块小围巾的面积之和越大越好。
这块围巾是一个正三角形,三条边被均匀地分成了N段,即这个正三角形被均匀地分成了N2个单元,每个单元是一个面积为1的正三角形。图一所 示为一个N=5的围巾,图中带阴影的单元表示被蛀虫咬坏的部分。从上往下看,围巾被分成了N行,第一行有1个单元,第二行有3个单元,其中有2个是形如D 的,有1个是形如Ñ 的(这两种三角形我们认为是形状相同的)。第三行有5个,其中有3个是形如D 的,有2个是形如Ñ 的…… 。用坐标(X,Y)给每个单元定位,第一行的单元的坐标为(1,1);第二行从左到右的三个单元的坐标依次为(2,1)、(2,2)、(2,3);…。
围巾的剪裁条件如下:
- 裁成的两块小围巾形状与原来的大围巾完全相同,都是正三角形。
- 每一块小围巾里都不存在被蛀虫咬坏的部分。
- 裁剪时必须沿着单元的边界裁剪。
- 要求两块小围巾的面积的总和最大。
图中,最优的裁剪方法已经用粗线画了出来,面积和为4+9=13。
现在需要你编一个程序来帮助裁缝解决这个问题。
输入
输入文件第一行为一个整数N(1<=N<=100),表示这块围巾总共被分成了N2个单元。第二行为一个整数M(0<= M<=N2-2),表示这块围巾共有M个单元被蛀虫咬坏了。接下的M行,每一行有两个正整数X和Y,为这M个被蛀虫咬坏的单元的坐标。
输入文件中同一行相邻两项之间用一个或多个空格隔开。
输出
输出文件仅含一个整数,为你所找到的裁出两块小围巾面积总和的最大值。
样例输入
5 5 3 2 4 1 4 4 5 4 5 2
样例输出
13