AT_tkppc3_j 円の重なり

[problemUrl]: https://atcoder.jp/contests/tkppc3/tasks/tkppc3_j 配点： $ 1300 $ 点 **この問題はリアクティブ問題です.** 平面上に $ N $ 個の円がある. これらの円の中心はすべて整数座標であり, x, y 座標は $ -1\ 000 $ 以上 $ 1\ 000 $ 以下である. また, 円の半径もすべて $ 200 $ 以上 $ 1\ 000 $ 以下の整数である. パ研の新入生の PAKEN 君は全ての円の情報を突き止めようと思っているが, 彼は円の個数 $ N $ しかしらない. 彼は E869120 に対して以下の質問をすることができる. - 座標 $ (p,\ q) $ はいくつの円の内部に含まれているか, という質問をすることができる. 境界の場合も含まれていると見做す. $ -5\ 000\ \leq\ p,\ q\ \leq\ 5\ 000 $ を満たす必要がある. $ p,\ q $ は整数である必要はない. PAKEN 君のために, できるだけ少ない回数の質問で全て円の情報を突き止めるプログラムを書け. ### Input & Output Format **この問題はインタラクティブ問題である. そのため普通の問題とは入出力形式が違う.** 1\. まず, あなたは, 以下のような入力を受け取らなければならない. > $ N $ $ N $ は, 平面上に存在する円の個数を表す. 2\. 次に, あなたは質問をしなければならない. まず, 質問をするためには以下のように出力しなければならない. > $ ? $ $ p $ $ q $ あなたは $ '?',\ p,\ q $ を**空白区切りで一行に**出力しなければならない. これは, 座標 $ (p,\ q) $ はいくつの円の内部に含まれているか, という質問をすることを意味する. $ p,\ q $ は小数でもよいが, 絶対値が $ 5\ 000 $ 以下でなければならない. 3\. 質問への答えは, 以下のようにしてジャッジから入力として受け取らなければならない. > $ R $ $ R $ は, 質問した座標は何個の円の内部に含まれているかを表す整数である. 質問への答えが終わったら, 2. もしくは 4. に行かなければならない. 4\. 答えが分かったら, 分かったタイミングで質問の代わりに解答を行わなければならない. 解答をするためには, 以下のような出力を行わなければならない. > $ ! $ $ x_1 $ $ y_1 $ $ r_1 $ $ x_2 $ $ y_2 $ $ r_2 $ ... $ x_N $ $ y_N $ $ r_N $ $ (x_i,\ y_i) $ は $ i $ 個目の円の中心座標, $ r_i $ は $ i $ 個目の円の半径を意味する. 解答を行う際には, $ N+1 $ 行にわたって出力しなければならない. $ 1 $ 行目には, $ '!' $ と出力しなければならない. $ 2 $ 行目からは, $ N $ 行にわたって円の情報 $ (x_i,\ y_i,\ r_i) $ をその順に空白区切りで出力しなければならない. **ただし, 出力する順番は中心座標の $ x $ 座標の小さい順, $ x $ 座標が同じであれば $ y $ 座標の小さい順に出力しなければならない.**

N/A

N/A

### 制約 - $ N $ は $ 1 $ 以上 $ 20 $ 以下の整数. - 円の座標 $ (x_i,\ y_i) $ と円の半径 $ r_i $ は, 問題文中に書かれている制約を満たす. - 全てのケースは, 制約の範囲内で, 一様な確率でランダムに生成されたものである. 具体的には, それぞれの円に対して, まず中心座標が $ (-1000,\ -1000) $ から $ (1000,\ 1000) $ までの $ 4004001 $ 個の中から一様な確率分布でランダムに選ばれ, 次に半径が $ 200 $ から $ 1000 $ までの $ 801 $ 通りの選択肢の中から一様な確率分布で選ばれる. ### 注意 - 出力形式を間違えたりした場合にジャッジ結果は不定である. (`WA` とは限らない) - **また, 出力の最後に flush をする必要があり, そうしない場合 TLE となる場合がある.** - **あなたは, $ 50\ 000 $ 回を超える質問をしてはならない.** ### 小課題 / 得点 小課題1 \[ $ 200 $点 \] - $ N\ =\ 1 $ である. - 小課題 1 のケースは $ 10 $ 個ある. $ 10 $ 個全てのケースに対して, $ 50\ 000 $ 回以内の質問で答えを求めることができれば, 正解となる. 小課題2 \[ $ 1\ 100 $点 \] - $ N\ =\ 20 $ である. - 小課題 2 のケースは $ 20 $ 個ある. $ 20 $ 個全てのケースで $ 50\ 000 $ 回以内の質問で答えを求めることができれば正解となるが, 質問回数によって下記のように得点が変わる. 一番多くの質問回数を要したケースにおける質問回数を $ L* $ とおくとき, 得点は以下のように変動する. - $ 25\ 001\ \leq\ L*\ \leq\ 50\ 000 $ のとき, $ 200 $ 点. - $ 9\ 001\ \leq\ L*\ \leq\ 25\ 000 $ のとき, $ 280 $ 点. - $ 3\ 001\ \leq\ L*\ \leq\ 9\ 000 $ のとき, $ 350 $ 点. - $ 2\ 001\ \leq\ L*\ \leq\ 3\ 000 $ のとき, $ 450 $ 点. - $ 601\ \leq\ L*\ \leq\ 2\ 000 $ のとき, $ 300\ +\ floor(\frac{480000}{L*}) $ の $ 1 $ の位を切り捨てて $ 10 $ の位までの概数にした得点. - $ L*\ \leq\ 600 $ のとき, $ 1\ 100 $ 点満点. ### 入出力の例 例として, $ N\ =\ 2 $ であり, 片方の円の中心座標が $ (4,\ 7) $ で半径が $ 2 $, もう片方の円の中心座標が $ (3,\ 8) $ で半径が $ 3 $ である場合の入出力（インタラクティブ）の一例を示す. 入力 出力 備考 2 $ N $ の値を入力. ? 0 0 座標 $ (0,\ 0) $ はいくつの円に含まれているか質問する. 0 どちらの円にも含まれない. 当然 $ 0 $ 個である. ? 4 6.5 座標 $ (4,\ 6.5) $ はいくつの円に含まれているか質問する. 2 どちらの円にも含まれているので, $ 2 $ 個である. ? 1.5 10 座標 $ (1.5,\ 10) $ はいくつの円に含まれているか質問する. 1 $ (3,\ 8) $ を中心とする半径 $ 3 $ の円にのみ含まれているので, $ 1 $ 個である. ! 3 8 3 4 7 2 $ (3,\ 8) $ を中心とする半径 $ 3 $ の円と, $ (4,\ 7) $ を中心とする半径 $ 2 $ の円があると答える. 中心の x 座標の小さい順, もしそれも同じであれば中心の y 座標の小さい順に出力する必要があることに注意せよ.