Centroid Point Query

2 secs 1024 MB
uruzunyaa's icon uruzunyaa

問題文

xyxy 平面上に NN 個の点があり、点 ii は座標 (Xi,Yi)(X_i,Y_i) にあります。

以下の QQ 個のクエリについて答えてください。

  • 44 頂点 (A,B),(C,B),(C,D),(A,D)(A,B),(C,B),(C,D),(A,D) からなる長方形領域、またはその周上に含まれる点の重心のうち yy 座標のみを答えてください。点が存在しない場合はそのことを報告してください。

※点の重心とは xx 座標と yy 座標それぞれについて、平均を取ったものを表します。
より厳密には、点 11 から 点 NN までの重心は(X1+X2++XNN,Y1+Y2++YNN)(\frac{X_1+X_2+ \ldots +X_N}N,\frac{Y_1+Y_2+ \ldots +Y_N}N) で定義されます。

制約

  • 入力は全て整数である。
  • 1N1051 \leqq N \leqq 10^5
  • 1013Xi,Yi1013-10^{13} \leqq X_i,Y_i \leqq 10^{13}
  • 1Q200001 \leqq Q \leqq 20000
  • 1013Ai<Ci1013-10^{13} \leqq A_i < C_i \leqq 10^{13}
  • 1013Bi<Di1013-10^{13} \leqq B_i < D_i \leqq 10^{13}

入力

入力は以下の形式で標準入力から与えられる。

NN
X1  Y1  X_1\; Y_1\;
X2  Y2  X_2\; Y_2\;
\vdots
XN  YN  X_N\; Y_N\;
QQ
A1  B1  C1  D1  A_1\; B_1\; C_1\; D_1\;
A2  B2  C2  D2  A_2\; B_2\; C_2\; D_2\;
\vdots
AQ  BQ  CQ  DQ  A_Q\; B_Q\; C_Q\; D_Q\;

出力

全体で QQ 行出力してください。 このうち ii 行目には、 ii 個目のクエリについて以下の形式に従って出力してください。

  • 範囲内に点が存在する時、 xx 座標、 yy 座標の順で、空白区切りで出力してください。
    ※この時、真の値との絶対誤差または相対誤差が 10610^{−6} 以下のとき正解と判定されます。

  • 範囲内に点が存在しない時、NoPoint を出力してください。

入出力例1

入力例1
4
1 1
1 2
2 3
4 1
3
0 2 3 3
-10 -10 0 0
1 1 4 2
出力例1
2.500000
NoPoint
1.333333

11 つ目のクエリにおいて、長方形範囲に含まれるのは、点 22 , 点3322つです。重心の座標は (1+22=1.5,2+32=2.5)(\frac{1+2}2=1.5,\frac{2+3}2=2.5) です。
yy 座標のみを答えるため、2.5000002.500000を出力します。
2.52.52.50000000000000002.5000000000000000 も正答と判定されます。

22 つ目のクエリにおいて、長方形の中に含まれる点はありません。よって NoPoint を出力します。
 

入出力例2

入力例2
3
0 0
0 0
-1 -1
1
-1 -1 0 0
出力例2
-0.333333

点は同じ場所に複数存在する事もあります。

同じ場所に存在する複数の点も、異なる点として重心を求める事に注意してください。  

Submit


Go (1.21)