SRM 436 DIV1 Easy - BestView （復習○）
問題
http://community.topcoder.com/stat?c=problem_statement&pm=10341&rd=13698
間隔１で一列に高層ビルが並んでいる。
高層ビルの上から他のビルをできるだけ多く見渡したい。
他のビルを見渡すには、そのビルと他のビルの屋上を結んだときに間に他のビルがなければよい。
このとき、一番多く見渡せるビルの数を求める。
解き方
各ビルにおいて見渡せるビルの数を全探索する。
最初は三平方の定理を使ってしまったが、座標の傾きを使えば簡単に他のビルがさえぎっているかどうかを判定することができる。
aからbを見渡す時、uがさえぎっていないかを判定するには
(h(u)-h(a))/(b-a) *x +h(a) <= h(u)
ここでx=(u-a)のときにビルuがさえぎってしまうので
(h(u)-h(a))/(b-a) *(u-a) +h(a) <= h(u)
(h(u)-h(a))/(b-a) *(u-a) <= h(u) -h(a)
(h(u)-h(a)) *(u-a) <= (h(u) -h(a)) *(b-a)
この式で判定できる。
見渡すビルを固定した時に他のビルを見渡せるかの判定については、
最初順序を決めて左と右の走査と分けてしまったが
間のビルがさえぎっていないかどうかだけを判定すればよいので
それがわかればよりシンプルに実装することができる。
コード
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class BestView {
public:
int numberOfBuildings(vector<int> h) {
int n=h.size();
int ret=0;
FORE(i,0,n){
int cnt=0;
FORE(j,0,n){
if(i==j)continue;
int a=i,b=j,valid=1;
if(a>b)swap(a,b);
FORE(u,a+1,b)if((long long)(h[b]-h[a])*(u-a)<=(long long)(h[u]-h[a])*(b-a))valid=0;
cnt+=valid;
}
ret=max(ret,cnt);
}
return ret;
}
};
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class BestView {
public:
int numberOfBuildings(vector<int> h) {
int n=h.size();
int ret=0;
FORE(i,0,n){
int cnt=0;
FORE(j,0,n){
if(i==j)continue;
int a=i,b=j,valid=1;
if(a>b)swap(a,b);
FORE(u,a+1,b)if((long long)(h[b]-h[a])*(u-a)<=(long long)(h[u]-h[a])*(b-a))valid=0;
cnt+=valid;
}
ret=max(ret,cnt);
}
return ret;
}
};
