ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

AOJ 3043 - Donut Hole

問題
提出コード

解法

まず、求める直線はすべて原点を通ります。ので、もともとあったドーナツは、その直線によって常に半分に切り分けられます。
ということは、1日目に食べた部分を2等分するような直線が、求める直線になります。
1日目に食べた部分は常に長方形になっているので、これまたその長方形の中心を通るような直線を求めれば、2等分することができます。
ということで求めるのは、

  • 原点と、1日目に食べた部分の中心点を通る直線の傾き

ですので、さらに言い換えて

  • 1日目に食べた部分の中心点の、y座標をx座標で割ったもの

になります。
あとは中心点を求めればいいのですが、サンプル2のケースのように、与えられた部分がすべてもともと存在したドーナツ上の範囲内であるとは限らないことに気を付けます。
1日目に食べた部分の端の辺は、最大値と最小値をうまく組み合わせることで求めることができるので、その中心が真ん中の座標になります。
あとは、double型になおし、精度に気を付けつつ答えを求めれば、答えとなります。