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

ベクトル 幾何 複素数

f:id:peroon:20191126035334p:plain

設定

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

解法

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

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✅