2点を通る円の中心を(2つ)求める AOJ 1132 Circle and Points 円で囲める点の最大値

f:id:peroon:20191126035334p:plain

設定

  • 2次元平面上の2点を与えられた時、そこを通る円が存在するなら2つある
  • その円の中心2つを求めたい
  • 半径rは与えられるとする

解法

  • 2次元ベクトルで考える(プログラム的には複素数complexを利用する)
  • 2点の中央cから垂直方向に単位ベクトルnを考える(画像参照)
  • それを長さx分だけ伸ばしたところが円の中心で、xはピタゴラスの定理から求まる
  • 垂直ベクトルについて、(a, b)に垂直なベクトルは(-b, a)である(内積が0)

code

typedef complex<double> C;
#define X real()
#define Y imag()

// 2点を与えると, それを通る半径rの円の中央2つを返す
vector<C> f(C a, C b, double r){
  vector<C> ret;
  
  // a, bの距離が大きすぎると作れない
  {
    double d = abs(a-b);
    if(d>2*r) return ret;
  }

  C c = (a+b)/2.0;

  double temp = r*r - norm(a-c);
  double x = sqrt(temp);

  //中央に向かうベクトル
  C d = c-a;
  C e = {-d.Y, d.X}; // 垂直ベクトル
  C f = e / abs(e); // 単位ベクトル

  ret.push_back(c+x*f);
  ret.push_back(c-x*f);

  return ret;
}

verified✅