aoj

CGL_7_E Cross points of circles

CGL_7_E Cross points of circles
Feb. 2, 2020, 1:52 p.m.

目次

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_7_E

解説

アルゴリズムの詳細は以下を参照.

2円の交点を求めるアルゴリズム

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
Int N;
double R1, R2;
Vector2 C1, C2;

pair<Vector2, Vector2> crossPoints() {
  Vector2 baseVec = C2 - C1;
  double baseLen = baseVec.length();
  double cos_ = (baseLen*baseLen + R1*R1 - R2*R2) / (2 * baseLen * R1);
  double sin_ = sqrt(1 - cos_*cos_);
  // Counter-clockwise
  Vector2 a_(cos_ * baseVec.x + -sin_ * baseVec.y, sin_ * baseVec.x + cos_ * baseVec.y);
  // Clockwise
  Vector2 b_(cos_ * baseVec.x + sin_ * baseVec.y, -sin_ * baseVec.x + cos_ * baseVec.y);
  Vector2 a = C1 + a_ * R1 / baseLen;
  Vector2 b = C1 + b_ * R1 / baseLen;
  if (fabs(a.x) < EPS) a.x = 0.0;
  if (fabs(a.y) < EPS) a.y = 0.0;
  if (fabs(b.x) < EPS) b.x = 0.0;
  if (fabs(b.y) < EPS) b.y = 0.0;
  if (a < b) return make_pair(a, b);
  return make_pair(b, a);
}

void solve() {
  auto points = crossPoints();
  cout << points.first.x << ' ' << points.first.y << ' ';
  cout << points.second.x << ' ' << points.second.y << endl;
}

void input() {
  cin >> C1 >> R1 >> C2 >> R2;
}

int main() {
  cout.precision(15);
  input();
  solve();
}