外積 aoj 線分の交点 cgl_2_c

CGL_2_C 線分の交点

CGL_2_C 線分の交点
Feb. 2, 2020, 1:52 p.m.

目次

問題

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

2つの線分の交点を求める問題.
必ず交点をもつ線分が与えられる.

解説

線分の交点の座標を求めるアルゴリズムについては以下を参照.


線分の交点を求めるアルゴリズム

最後に$p.x, p.y$が0の誤差範囲内であれば0と出力することを忘れずに.

解答

 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
Int N;
Vector2 p0, p1, p2, p3;

Vector2 crossPoint() {
  Vector2 baseSeg = p1 - p0;
  Vector2 crossSeg = p3 - p2;
  double h2 = fabs(baseSeg.cross(p2 - p0)) / (baseSeg.length() * 2);
  double h3 = fabs(baseSeg.cross(p3 - p0)) / (baseSeg.length() * 2);
  return p2 + crossSeg * h2 / (h2 + h3);
}

void solve() {
  Vector2 p = crossPoint();
  if (fabs(p.x) < EPS) cout << 0;
  else cout << p.x;
  cout << ' ';
  if (fabs(p.y) < EPS) cout << 0;
  else cout << p.y;
  cout << endl;
}

void input() {
  cin >> N;
  while (cin >> p0 >> p1 >> p2 >> p3) {
    solve();
  }
}

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