TopCoder SRM621 DIV1 EASY - RadioRange

Source

TopCoder SRM621 DIV1 EASY (275pt)
Problem Statement

問題概要

$2$ 次元平面上の点 $(0,0)$ にラジオ局の電波塔がある.
また,$N$ 個の街があり,それぞれ街 $k$ は $(X_k,Y_k)$ を中心とする半径 $R_k$ の領域である.
街同士は,共通部分を持っていたり,包含関係にあったりする可能性もある.
ラジオ局からの電波は,ランダムに $0$ 以上 $Z$ 以下の実数 $s$ を選び,半径 $s$ の円の内部にのみ届くように電波を出す.
同時にすべての街において,その街の全体が電波を受信できるか,その街の全体が電波を受信できない状態になっている確率を求める問題.

解法

それぞれの街について,一部のみが電波を受信してしまう状態になる $s$ の区間を求める.
これは,$(0,0)$ から $(X_K,Y_k)$ までの距離 $\sqrt{X_k^2 + Y_k^2}$ から $\pm R_k$ の範囲.
範囲にマイナスや,$Z$ を超える部分が含まれる場合は適当に削り落とすなどの処理をする.
後は,その何処かの範囲に含まれている実数の部分の(数直線上での)長さ $t$ を求めて,$1 - t/Z$ を答えとすれば良い.
区間の始点でソートして,順番に見ていって,今まで含まれていない部分の長さを足していけば良い.

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

class RadioRange {
public:
double RadiusProbability(vector <int> X, vector <int> Y, vector <int> R, int Z) {
  int i, j, k, n;
  double mn, mx;
  pair<double,double> bad[1000];
  double res = 0;

  n = X.size();
  rep(i,n){
    mn = sqrt((double)X[i]*X[i]+(double)Y[i]*Y[i]) - R[i];
    mx = sqrt((double)X[i]*X[i]+(double)Y[i]*Y[i]) + R[i];
    mn = max(mn, 0.0);
    mx = min(mx, (double)Z);
    bad[i] = make_pair(mn, mx);
  }
  
  sort(bad, bad+n);
  mn = 0;
  rep(i,n){
    if(bad[i].first < mn) bad[i].first = mn;
    if(bad[i].first < bad[i].second){
      res += bad[i].second - bad[i].first;
      mn = bad[i].second;
    }
  }

  res = 1 - res/Z;

  return res;
}

}

Current time: 2017年07月23日15時47分16秒
Last modified: 2014年05月24日04時37分33秒 (by laycrs)
Tags: Competitive_Programming TopCoder Single_Round_Match SRM621 SRM_Div1_Easy
トップページに戻る

Logged in as: unknown user (not login)

ログイン: