新規
編集
添付
時間制限:1000ミリ秒
メモリ制限:10000KB
石の持ちあげ
問題 
床には、大きな重い石によって塞がれた隙間がある。石を持ちあげると、特殊な仕掛けによってそのことが検出され、隙間から有毒な矢が発射される。そのため、石を非常にゆっくり、慎重に持ちあげる必要がある。ACMチームは石にロープを繋いで、滑車を用いて持ちあげなければならない。しかも、石は一気に持ちあげなければならない、つまりある側が反対側より早く持ちあがってはいけない。そのため、重心を見つけてそこにロープで繋ぐことが重要になる。石は多角形をしていて、その高さは多角形全体を通じて一定である。あなたの仕事は、与えられた多角形の重心を求めることである。
入力
入力はT個のテストケースからなる。入力の最初の行で、数字Tが与えられる。各テストケースは、多角形の頂点数をあらわす1つの整数N(3 <= N <= 1000000)を含む行から始まる。続くN行は、それぞれ2つの整数XiとYi(|Xi|, |Yi| <= 20000)が空白を区切りとして書かれている。これらの数字は多角形のi番目の頂点の座標をあらわす。この頂点を順番に繋ぐことで、多角形を得る。辺同士は隣接するもの以外接することはなく、交差することもないとしてよい。多角形の面積はゼロではない。つまり多角形は単一の直線になることはない。
出力
それぞれのテストケースについて、1行ずつ出力せよ。それぞれの行は空白で区切られた2つの数字を含んでいる。数字は重心の座標をあらわしている。座標を、最も近い小数点以下2桁の数字に丸めること。(0.005は切り上げられて0.01になる。)多角形が凸でない場合、重心は多角形の外側になるかもしれないことに注意すること。そのようなケースが入力にあった場合でも、そのまま重心を出力すればよい。
入力例
2 4 5 0 0 5 -5 0 0 -5 4 1 1 11 1 11 11 1 11
出力例
0.00 0.00 6.00 6.00
出典
Central Europe 1999
