UVa12302 Nine-Point Circle

問題概要
三角形が与えられる。九点円の中心と半径を求めよ。

解法
三角形の各辺の中点を通る円を求めればよい。
中点は3つあるので、3点を通る円を垂直二等分線の交点から求める。

#include <iostream>
#include <algorithm>
#include <complex>
#include <cstdio>

using namespace std;

typedef complex<double> P;

typedef pair<P, P> LINE;
#define F first
#define S second

inline double cross(P a, P b) {
  return (conj(a)*b).imag();
}

inline P getIntersection(LINE l1, LINE l2) {
  P& p1 = l1.F;
  P& p2 = l1.S;
  P& q1 = l2.F;
  P& q2 = l2.S;
  return p1 + (p2-p1)*(cross(q2-q1, q1-p1) / cross(q2-q1, p2-p1));
}

int main() {
  
  int x1, y1, x2, y2, x3, y3;
  while(cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3) {
    if(x1 == -1) break;
    P A(x1, y1), B(x2, y2), C(x3, y3);
    P MAB((A+B)/2.), MBC((B+C)/2.), MCA((C+A)/2.);
    P V1(MBC-MAB), V2(MCA-MBC);
    P D((MAB+MBC)/2.), E((MBC+MCA)/2.);
    LINE l1(D, D+V1*P(0,1)), l2(E, E+V2*P(0,1));
    P O = getIntersection(l1, l2);
    double radius = abs(O-MAB);
    printf("%.6f %.6f %.6f\n", O.real(), O.imag(), radius);
  }
  
  return 0;
}