解法概要

各都市の範囲は凸多角形を用いて管理しました．
クエリの前半ではその面積の削減を重視し，後半では近い都市間の距離情報の獲得を重視しました．
その後全都市対間距離を大まかにソートし，それを元にグループ分けを改善，グループ内全域木を作成しました．

解法詳細

都市の扱い

範囲を凸多角形とし，1点として扱いたい場合にはその重心とします．
占い結果が出揃いソートをするまで，都市間の距離としてはこの重心間の距離（の2乗）を用います．

占い結果の扱い

占い結果の各頂点\(v\)について以下の2パターンの不等式を記録します．（頂点\(i\), \(j\)間の距離を\(d_{ij}\)とします．）

• \(v\)の隣接頂点\(u_i\), \(u_j\)について，\(d_{vu_i} \leq d_{u_iu_j}\) かつ \(d_{vu_j} \leq d_{u_iu_j}\)．
• \(v\)の隣接頂点\(u\)と，\(v\)を根として見た時の部分木\(u\)内の頂点\(c\)について，\(d_{vu} \leq d_{vc}\)．
  

また，それぞれ3都市で多角形内に一様ランダムに点を生成して多角形の頂点と合わせ，不等式の条件を満たすペアが存在しない点を削除し，残った点がつくる凸包を新たな多角形とします．すべて削除されてしまう場合には重心の1点とします．
点の生成は多角形の頂点と合わせて20点までとし，多角形のバウンディングボックス内に100回を上限に点を生成し多角形内に入ったものを採用しました．（多角形の頂点数は概ね10程度以下となっていました．）
（各都市の点の数を\(n\)として，\(O(n^3)\)の全探索を行っています．枝刈りが強く働いているのか，例えば2つめのパターンにおいて\(v\)の各点で\(u\)の最近点と\(c\)の最遠点とを比較するというような\(O(n^2)\)のものよりも高速に動作していました．）

クエリ前半（面積削減重視）

範囲の小さな都市を基準にして大きな都市の範囲を削ります．
クエリ作成の度に面積でソートし，4割を小さな都市，5割を大きな都市としました．
具体的には，下記のルールで大きな都市1つと小さな都市2つとをセットにして，重複は飛ばしつつクエリに入れていきます．
クエリ100回を上限とし，クエリを埋めるセット数が不足した場合はそのクエリを消しクエリ後半に移りました．

大きな都市

まだこれまでのクエリで大きな都市として選ばれていないものの中で最も大きなものを選びます．

小さな都市

大きな都市を頂点とする二等辺三角形を作ります．
選ばれた大きな都市との距離でソートし，隣り合う2都市のうち以下の条件を満たす，最も距離の差の小さなものを選びました．

• 大きな距離との距離がある程度小さい．（小さな都市のうち上位1/4までとしました．）
  
• 小さな都市間の距離が大きな都市との距離よりも小さい．
  

1つめの条件は同時にクエリに入れた都市セットの邪魔をできるだけしないため， 2つめの条件は占いで大小間の二等辺がどちらも選ばれてしまい削れる面積が少なくなるのを避けるために課しています．
クエリサイズが中途半端に余っている場合は，1つめの条件を満たさなかったものを順番にクエリに加えました．

クエリ後半（近い都市重視）

始点として，まだ後半のクエリで始点に選ばれていないものの中で最も大きな都市を選び，そこからの距離が近い順にクエリサイズまで他の都市を選びます．
この際，占い結果からより始点に近い都市の存在が分かっているような都市は飛ばしました．

都市間距離のソート

占い結果から得られた不等式の左辺から右辺へ辺を張ったグラフ（距離の近い都市対から遠い都市対へ辺を張ったグラフ）を考え，トポロジカルソートの要領でソートをします．
具体的には，座標での距離が一番近い都市対を取り出せるようなpriority_queueを用意し，入次数が0の都市対を入れ，「都市対を1つ取り出す→グラフからその都市対とそこから出ている辺を消す→入次数が0になった都市対を入れる」を繰り返すことで都市対を並べます．

グループ分け

初期状態として，辞書順に「まだ使われていない都市を1つ選ぶ→そこから近い順にグループサイズまで他の都市を選ぶ」を繰り返したものを用意します．
そこから制限時間まで以下を繰り返します．

• グループを1つランダムに選び，それとグループの重心間の距離が近いグループを1つ選ぶ．（選んだグループに近い2グループからランダムとしました．）
• 2つのグループを合わせた都市集合から座標で最遠となる都市対を始点として選び，2つの木を作ることでグループを分割する．

グループの分割では具体的には，

• 都市間距離のソートで並べた順にコストを\(1,2,...,N(N-1)/2\)としてあらかじめ割り振っておく．
• グループサイズの割り振り方2通りについて以下を試し，コストの和が小さい方を採用する．
• コストの小さい順に取り出せるpriority_queueを用意し，既に木に組み込まれた各都市（始点の2都市からスタート）と残っている各都市との関係（コスト，加えたい都市，どちらの木に属する都市との情報か）を入れる．
• 1つ取り出し，まだ残っている都市ならば木に加え，情報をキューへ加えることを繰り返す．（加えたい木が既にグループサイズに達していたら飛ばす．）

としました．