外積 内積 ベクトル aoj cgl_1_c

CGL_1_C 反時計回り

CGL_1_C 反時計回り
Feb. 2, 2020, 1:52 p.m.

目次

問題

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

2つのベクトルがどういう位置関係にあるのかを判定する問題.

  1. 反時計回り
  2. 時計回り
  3. 正反対
  4. 同じ向き(p1が遠い)
  5. 同じ向き(p2が遠い)

解説

反時計回り、時計回り、同直線上はベクトルの外積を計算することですぐに分かる.
外積が負なら時計回り、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
33
Int N;
Vector2 p0, p1, p2, v01;
string msgs[5] = {"COUNTER_CLOCKWISE", "CLOCKWISE", "ONLINE_BACK", "ONLINE_FRONT", "ON_SEGMENT"};

int clk(Vector2 &v01, Vector2 &v02) {
  double cross_ = v01.cross(v02);
  if (cross_ > 0.0) return 0;
  else if (cross_ < 0.0) return 1;

  double dot_ = v01.dot(v02);
  if (v01.dot(v02) < 0.0) return 2;
  if (v01.length() - v02.length() >= 0) return 4;
  return 3;
}

void solve() {
  Vector2 v02 = p2 - p0;
  int msg_idx = clk(v01, v02);
  cout << msgs[msg_idx] << endl;
}

void input() {
  cin >> p0 >> p1 >> N;
  v01 = p1 - p0;
  while (cin >> p2) {
    solve();
  }
}

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