google code jam 2010 Round 1C Rope Intranet

program

問題

http://code.google.com/codejam/contest/dashboard?c=619102#s=p0

  • ビルが2つ並んでいて、左のビルの高さA[i]の所から右のビルの高さB[i]の所に電線が張ってある。
  • 電線の交点の数を求めなさい、という問題。
  • 但し、3つの線が一点で交わる事はない事は保証されている。

方針

  • 素直に数える。
  • i番目の線とj番目の線が交わるかどうかは、A[i] - A[j]とB[i] - B[j]が同符号か否かで判定。
    • (A[i] - A[j] > 0) と (B[i] - B[j] > 0)のXORでも良い。
  • 今回は、サイズが小さいので数え上げで問題なかったけど、サイズが大きい場合、Binary Indexed Treeで解けるらしい。
    • セグメント木とBITについては以前も勉強したのに、全然、そんな解法思い付かなんだ。泣
    • この解法について解説してくれたのは、弱冠二十歳でプログラミング歴3年くらいの若者でした。凄。

回答例

/*! g++ main.cpp -DNDEBUG
 */

#include <vector>
#include <iostream>
#include <fstream>
#include <string>

using namespace std;
typedef unsigned long ul;

void solve(int t){
  int n;
  cin >> n;

  vector<int> a(n), b(n);
  for(int i = 0; i < n; i++){
    cin >> a[i] >> b[i];
  }

  int ret = 0;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < i; j++){
      ret += (a[i] - a[j]) * (b[i] - b[j]) < 0 ? 1 : 0;
    }
  }

  cout << "Case #" << t << ": " << ret << endl;
}

int main(int argc, char* argv){

  int num_case;
  cin >> num_case;

  for(int i = 0; i < num_case; i++){
    solve(i + 1);
  }

  return 0;
}