AOJ : 2003 - Railroad Conflict

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2003&lang=jp
日本語の問題文があるので省略です

アルゴリズム

1. A地点から交差点までの距離を、ライバルと自社とに分けて、全て列挙 (ABと交差しないのは無視)
2. ライバルの交差点までの距離を配列 r に、自社の交差点までの距離を配列 s に入れる
3. A地点から距離が近い順に、r と s をソート
4. i=0,j=0
5. r[i] と s[j] を見て、A地点から近い方を選ぶ
   • r[i] を選んだなら、それと反対側を通る -> i++
   • s[j] を選んだなら、それと同じ側を通る -> j++
   • トンネル作る必要があるならカウント
6. 5を繰り返す

プログラム

#include <iostream>
#include <complex>
#include <vector>
#include <algorithm>
using namespace std;

#define EPS (1e-10)
#define INF (P(999999999,999999999))

typedef complex<double> P;

double cross(P a, P b) {
  return (a.real() * b.imag() - a.imag() * b.real());
}

int is_intersected_ls(P a1, P a2, P b1, P b2) {
  return
    ( cross(a2-a1, b1-a1) * cross(a2-a1, b2-a1) < EPS ) &&
    ( cross(b2-b1, a1-b1) * cross(b2-b1, a2-b1) < EPS );
}

P intersection_ls(P a1, P a2, P b1, P b2) {
  P b = b2-b1;
  double d1 = abs(cross(b, a1-b1));
  double d2 = abs(cross(b, a2-b1));
  if(d1 + d2 == 0) return INF;
  double t = d1 / (d1 + d2);

  return a1 + (a2-a1) * t;
}

int main(void){
  int n;
  cin>>n;

  while(n--){
    P sa,sb;
    cin>>sa.real()>>sa.imag()>>sb.real()>>sb.imag();

    int m;
    cin>>m;

    vector< pair<double,bool> > s,r;
    while(m--){
      bool flgRS,flg; //flgRS : 0 - ライバル 1 - 自分
      P a,b;
      cin>>a.real()>>a.imag()>>b.real()>>b.imag()>>flgRS>>flg;

      if(is_intersected_ls(a,b,sa,sb)){
        P its = intersection_ls(a,b,sa,sb);
        if(its == INF) continue;

        double dist = abs(sa - its);
        if(flgRS)
          s.push_back(pair<double,bool>(dist,flg));
        else
          r.push_back(pair<double,bool>(dist,flg));
      }
    }

    sort(s.begin(),s.end());
    sort(r.begin(),r.end());

    bool flg = false, firstFlg = true;
    int ans = 0, i = 0, j = 0;

    while(i < r.size() || j < s.size()){
      if(j == s.size() || i != r.size() && r[i].first < s[j].first){
        if(!firstFlg && flg != !r[i].second) ans++;
        flg = !r[i].second;
        i++;
      }
      else{
        if(!firstFlg && flg != s[j].second) ans++;
        flg = s[j].second;
        j++;
      }

      firstFlg = false;
    }

    cout<<ans<<endl;
  }

  return 0;
}