読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

Codeforces 498A : Crazy Town

問題リンク : Problem - 498A - Codeforces

問題概要 :
2次元平面上の異なる2点とn本の直線が与えられる
2つの直線が同一であることはないし、2点が線分上に存在することもない
2点のうち片方からもう片方へ移動する際にまたがなければならない線分の数の最小値を求めよ
ただし線分と線分の交点を移動することはできない

解法 :
2点の間を通る直線の数を数える
自分は線分上の異なる2点を選んでccwで線分と各点との関係が異なるかどうかで判定した
関係が異なるなら+1

コード :

int main(){
  Point sp,ep;
  cin >> sp.x >> sp.y;
  cin >> ep.x >> ep.y;
  int n;
  cin >> n;
  int answer = 0;
  rep(_,n){
    double a,b,c;
    cin >> a >> b >> c;
    Point p1,p2;
    if( equals(a,0) ) {
      double y = - c / b;
      p1 = Point(0,y);
      p2 = Point(5,y);
    } else if( equals(b,0) ) {
      double x = - c / a;
      p1 = Point(x,0);
      p2 = Point(x,5);
    } else {
      p1 = Point(0,-c/b);
      p2 = Point(5,-(5*a+c)/b);
    }
    int res1 = ccw(p1,p2,sp);
    int res2 = ccw(p1,p2,ep);
    if( res1 != res2 ) ++answer;
  }
  printf("%d\n",answer);
  return 0;
}