Posted on 2010-07-03 11:00
王之昊 閱讀(301)
評論(0) 編輯 收藏 引用 所屬分類:
2：30
Stars
題意：給你一副星座地圖，還有若干星座，對于每個星座，尋找他在地圖中出現的次數。其中允許旋轉和縮放，若某個星座在地圖上的兩個映射A，B所包含的點集是一樣的，則A，B算一次。
大致思路是取出星座的第一，第二點，然后枚舉這兩個點在地圖中的位置，將其他的點旋轉過去檢查是否合法。計算出次數S。
然后在類似的計算出星座在自身中重復出現的次數B，最后答案為S / B
在具體實現上有幾個問題：
double round(double d){
return floor(d + 0.5);
}
- 用了vector，導致變慢， vector確實是慢了，改成數組 1000ms-->204ms
- 用了map和set導致變慢，將map改成手寫的hash，204ms-->110ms
- 遇到段錯誤，結果發現是數組越界，數組越界有上越界（比如數組開小了）和下越界（比如下標為負）