Treasure Hunt

Time Limit : 2 sec, Memory Limit : 65536 KB

I - 宝探し

問題文

わたしはある宝探しの依頼を受けた.
どうやら,この近くの地中 2W × 2H の範囲内にお宝が埋まっているらしい.
わたしの得意なダウジングを使えば,現在の位置からお宝がどの方向にねむっているのか知ることができる.

ただ,わたしの能力はその日の体調による影響が大きく,今日はダウジングをした時に最大で E 度まで誤差が出てしまいそうだ.
また,わたしの体力にも限界はある.1日に200回までしかダウジングを行うことはできない.

わたしは考えることは苦手だ.
あなたには,宝を見つけるためにどこでダウジングをするべきかの指示を出していただきたい.

入出力形式

最初の入力は以下の形式で与えられる.入力は全て小数12桁までの実数で与えられる.

W H E

この入力は,宝の埋まっている座標 (x,y) が,

  • -WxW
  • -HyH

を満たし,またダウジングの結果の誤差が E 度以下であることを表す.

以降,あなたはダウジングを行う場所を指定し結果を得るか,もしくは,宝の場所を確定したと伝えることができる.

地点 (x,y) でダウジングを行い,結果を得るには

printf("? %.12f %.12f\n", x, y); fflush(stdout);

とする.次に,

scanf("%lf", &degree);

とするとダウジングの結果が得られる.
結果の角度 degree は,(x,y) から宝のある方向をθ とした時,[θ-E,θ+E] の一様分布によって生成される.
宝のある地点でダウジングを行った場合,θ=0 となる.
角度はx軸正方向が0度,y軸正方向が+90度とする.
もし -180 ≤ degree ≤ 180 を満たしてない場合,この範囲に収まる様に degree は修正される.

地点 (x,y) に宝が存在すると伝える場合には

printf("! %.12f %.12f\n", x, y); fflush(stdout);

とする.
このとき,実際の宝の位置との絶対誤差が Lノルム で 0.5 以下になっていなければならない. なお,ダウジングや宝の位置の指定以外の出力を行った場合は誤答(Wrong Answer)と判定される.

制約

  • 0W104
  • 0H104
  • 0E120
  • 入力値は全て小数12桁までの実数である.
  • ダウジングは最大で 200 回まで行える.それを越えると誤答となる.

この問題の判定には,3 点分のテストケースのグループが設定されている.このグループに含まれるテストケースは上記の制約に加えて下記の制約も満たす.

  • E = 0

入出力例


プログラムの出力プログラムへの入力
100 100 0
? -97.30147375 -55.03559390
45.8958081317
? 44.46472896 -54.50272726
110.928234444
... ...
! 4.50000018 50.00000005

最初にプログラムは宝のある範囲 W,H とダウジングの精度 E を受け取る.
その後,プログラムは (-97.3, -55.0) で1回目のダウジングを行い,宝のある方向は 45.8 度の方向だという情報を得ている.
次に,プログラムは (44.5, -54.5) で2回目のダウジングを行い,宝のある方向は 110.9 度の方向だという情報を得ている.
その後何度かダウジングを行い,最終的に宝のある位置は (4.5, 50.0) であると出力している.


Writer : 森槙悟,楠本充,花田裕一朗

Source: Kyoto University Programming Contest 2012 , Kyoto, Japan, 2012-07-01
http://www.kupc.jp/
http://kupc2012.contest.atcoder.jp/