Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2407-ba729344
この記事にトラックバックする(FC2ブログユーザー)

SRM300 DIV2 EASY - Taxi (この記事を編集する[管理者用])

Source

TopCoder SRM300 DIV2 EASY (250pt)
Problem Statement

問題概要

2点間$(x_1, y_1)$と$(x_2, y_2)$との距離を2種類定義する:
 マンハッタン距離 $|x_1 - x_2| + |y_1 - y_2|$
 ユークリッド距離 $\sqrt{ (x_1 - x_2)^2 + (y_1 - y_2)^2 }$
${\rm maxX}, {\rm maxY}, {\rm taxiDist} \leq 1000000$が与えられる.
3条件
 (1) $0 \leq x_1, x_2 \leq {\rm maxX}$
 (2) $0 \leq y_1, y_2 \leq {\rm maxY}$
 (3) $(x_1, y_1)$と$(x_2, y_2)$とのマンハッタン距離が${\rm taxiDist}$
を満たすとき,$(x_1, y_1)$と$(x_2, y_2)$とのユークリッド距離の最大値はいくらか求める問題.
3条件を満たす2点$(x_1, y_1)$と$(x_2, y_2)$が存在しないときはそれを指摘する.

解法

$x_1 \leq x_2,\; y_1 \leq y_2$としてしまって良い.
最初の2条件は$d_x = x_2 - x_1 \leq {\rm maxX}, \; d_y = y_2 - y_1 \leq {\rm maxY}$となる.
$d_x$を決め打てば,$d_y = {\rm taxiDist} - d_x$で求まるので,$d_x$を(整数の範囲で)全探索する.
もしくは,できるだけ長細い($d_x$が最大,または,$d_y$が最大)の時が答えになるので,それを場合分けして求める.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

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

double dist(double i, double j){ return sqrt(i*i+j*j); }

class Taxi {
public:
double maxDis(int maxX, int maxY, int taxiDis) {
  int i, j, k;
  double res = -1;

  rep(i,maxX+1){
    j = taxiDis - i;
    if(j < 0 || j > maxY) continue;
    res = max(res, dist(i,j));
  }

  return res;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2407-ba729344
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。