PKU3251-Big Square

題目： http://poj.org/problem?id=3251
Farmer John擁有很多乳牛，事實上，Farmer Bob也有很多乳牛
他們倆決定來一場世紀乳牛大對決！
現在他們把各自的乳牛放置到一個N*N(100*100)網格的交會點上
希望能圍出一個最大的正方形四個角落都站著自己陣營的乳牛
正方形的邊不一定要和網格平行
(一格只會有0~1隻乳牛，所以只有 空格'*' FJ側'J' 和 FB側'B'三種符號)

現在所有的乳牛都站到網格上了，除了Farmer John的乳牛Bessie之外
把Bessie放進去以後FJ側能圍出多大面積的正方型呢？

(最大的正方形四角不一定要包含Bessie，
給出的測資一定會有至少一個'*'給Bessie站)



程式碼：http://codepad.org/3yVaj8Vd <--- 媽！我的程式跑了63MS我排名好前面啊
(codepad又復活了，真是可喜可賀)

正方形可能是斜斜的，但是面積卻總是正整數，請參考下面這條測資
5
*****
****J
*****
J****
***J*
答案是3*3+1*1=10

根據題意只要有至少三個J就能圍出正方型了
但是最後的空格不能被FB牛占據才可以

數據N只到100
解法的核心基本離不開「枚舉所有可能正方型並檢驗之」


解法一：枚舉所有J點對當正方形的對角線，檢驗各座標
(程式碼中的algorithm2)
O(N^4)，相當容易實作出來、利用中學幾何知識就可以了
稍微多注意一下對角線兩端點的「x距離+y距離」如果是奇數必須剪掉
因為這樣一來另外兩點的座標就會是小數了


解法二：
前面的方法全部測資在PKU跑完要500MS左右
壓到100MS以下甚至16MS的大有人在，怎麼辦到的？
關鍵就在「可能座標點是整數」
想針對答案比較大(接近9801)的測資進行優化
方法就是從面積9801,9800,9799,...逐一檢驗

如此一來，作法就類似
「枚舉所有J當中心點，對八方位的『畢氏三角型』進行檢驗」
而這種形式相當容易剪枝

需要檢驗的數對大概有多少呢？
我的程式跑了個表大概是長這樣的：

9801 formed by (0,99)
9801 formed by (99,0)
9800 formed by (14,98)
9800 formed by (70,70)
9800 formed by (98,14)
9797 formed by (31,94)
9797 formed by (49,86)
9797 formed by (86,49)
9797 formed by (94,31)
9792 formed by (24,96)
9792 formed by (96,24)
9781 formed by (41,90)
9781 formed by (90,41)
9778 formed by (47,87)
9778 formed by (87,47)
9773 formed by (13,98)
9773 formed by (62,77)
9773 formed by (77,62)
9773 formed by (98,13)

.
.
.
總約8000項，交換當一樣有將近4000項

實際上和作法一理論複雜度是差不了太多的



--

總結：我的程式碼是判斷J的數量比較稀疏時使用作法一
反之使用作法二
其中實作的細節(例如是不是同一個正方形判了很多次)對常數影響不小
多多注意應該就能達到16MS