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