SRM436 Div.1 Easy BestView

問題

xy平面上の(i,0)に高さh_i(i=1,2,...,n)のn本のビルがあるとき、あるビルから見える他のビルの屋上の最大数を求めよ

方針

あるビルに注目したときそのビルから左右方向に別々にループを回すのはめんどいので
ビルiからビルjの屋上が見える場合その逆も成り立つので、(i,j)の組み合わせすべてについて
間にあるビルが屋上を結ぶ直線と交わらなければ良い、のだが
愚直に式を立てると、i,j間のi+k番目のビルが射線と交わるかどうかは

height[i+k] >= height[i] + (height[j] - height[i]) * (k / (j-i))

になるのだがこのままやると誤差死する。というかした。なので

(j-i) * height[i+k] >= (j-i) * height[i] + (height[j] - height[i]) * k

としてやればいい。このときの各項はintでは収まらない可能性があるのでlonglongを使う。

以下ソースコード

     int numberOfBuildings(vector <int> heights) {
         int n = heights.size();
         int ret=0;
         bool cansee[n][n];
         bool able;
         ll diff;

         memset(cansee, false, sizeof(cansee));
         for(int i=0;i<n;i++){
             for(int j=i+1;j<n;j++){
                 able = true;
                 diff = heights[j] - heights[i];
                 for(int k=1;k<j-i;k++){
                     if((ll)(j-i) * heights[i+k] >= (ll)(j-i) * heights[i] + diff * k){
                         able = false;
                     }
                 }
                 if(able){
                     cansee[i][j] = true;
                     cansee[j][i] = true;
                     /*
                     if(heights[i] >= heights[j]) cansee[i][j] = true;
                     if(heights[j] >= heights[i]) cansee[j][i] = true;
                     */
                 }
             }
         }
         for(int i=0;i<n;i++){
             int cnt=0;
             for(int j=0;j<n;j++){
                 if(cansee[i][j] == true){
                     cnt++;
                 }
             }
             ret = max(ret,cnt);
         }
         return ret;
     }