AOJ0143 Altair and Vega

解法１
牽牛と織姫とをつなぐ線分と、三角形の３つの線分との交差を判定しカウントする。
一回の交差のみなら "OK" それ以外の回数の交差なら "NG" と出力する。

解法２
牽牛と織姫が、三角形の内部か外部かで同じ場所にいるかどうかを判定すれば良い。
例えば牽牛が内部に含まれているとき、牽牛と三角形の３点から３つの三角形が出来上がるので、その三角形の面積の和が与えられた三角形の面積に一致するか調べると内部にいるかどうかの判定ができる。
これを織姫にも適用し、どちらも内部 or どちらも外部なら "NG" 一方が内部で他方が外部なら "OK" と出力すれば良い。

解法３
解法２と同様の考えで内部か外部か判定するためにCCWをする。

以下は解法１の線分の交差判定のコード。

#include <bits/stdc++.h>
 
using namespace std;
 
#define FST first
#define SND second
 
#define EPS (1e-5)
 
typedef complex<double> P;
typedef pair<P,P> SEG;
 
double cross(P a, P b) {
  return a.real()*b.imag()-a.imag()*b.real();
}
 
bool isIntersectSS(SEG a, SEG b) {
  return (cross(a.SND-a.FST, b.FST-a.FST) * cross(a.SND-a.FST, b.SND-a.FST) < EPS)
    && (cross(b.SND-b.FST, a.FST-b.FST) * cross(b.SND-b.FST, a.SND-b.FST) < EPS);
}
 
int main() {
   
  int N; cin >> N;
   
  while(N--) {
    P Wall[3];
    for(int i=0; i<3; i++) {
      double x, y; cin >> x >> y;
      Wall[i] = P(x, y);
    }
     
    double x, y;
    cin >> x >> y; P altair(x, y);
    cin >> x >> y; P vega(x, y);
    SEG seg(altair, vega);
     
    int ok = 0;
    for(int i=0; i<3; i++) {
      ok += isIntersectSS(seg, SEG(Wall[i], Wall[(i+1)%3]));
    }
     
    if(ok == 1) {
      cout << "OK" << endl;
    }
    else {
      cout << "NG" << endl;
    }
  }
   
  return 0;
}