Problem 102

R Project Euler

3つの異なる点が -1000 ≤ x, y ≤ 1000 かつ三角形となるように, デカルト平面上にランダムに与えられる.
以下の2つの三角形を考える.

  • A(-340,495), B(-153,-910), C(835,-947)
  • X(-175,41), Y(-421,-714), Z(574,-645)

三角形ABCが原点を内部に含み, XYZは原点を内部に含まないことが確かめられる.
27Kのテキストファイルtriangles.txt(右クリックしリンク先を保存して欲しい) にランダムな1000個の三角形が適当なフォーマットのもと含まれている. 内部に原点を含む三角形の数を答えよ.
注: ファイル中の最初の二つは三角形ABC, XYZである.

ファイルはリンク先から．
今ひとつ上手い方法が思い付かなかったので’¼ü‚̃Aƒ‹ƒSƒŠƒYƒ€ ‰~‚̃Aƒ‹ƒSƒŠƒYƒ€などを参考にした．
430ms．

## y軸をまたぐ2本の直線の始点と終点を返す
## y軸をまたぐならy軸で頂点は1:2に分割される
## 1点の座標を最初に，他の2点の座標をその次に続くように整列して返す
sort.apices <- function(A){
  ans <- numeric(4)
  x <- A[c(1,3,5)]
  if(sum(x < 0) == 3 ||
     sum(x > 0) == 3){
    return(FALSE)                       # y軸をまたがない
  }
  if(sum(x > 0) == 1){
    p1 <- ((1:6)[A==x[x>0]]:((1:6)[A==x[x>0]]+1)) # 1点の座標を返す添字
    return(c(A[p1], A[-p1]))
  } else {
    p1 <- ((1:6)[A==x[x<0]]:((1:6)[A==x[x<0]]+1)) # 1点の座標を返す添字
    return(c(A[p1], A[-p1]))
  }
}

## 座標値(a1, a2, b1, b2)から切片を計算
intersept <- function(ap){
  return(ap[2] - (ap[2] - ap[4])/(ap[1] - ap[3])*ap[1])
}

## 点A, B, C = (a1, a2, b1, b2, c1, c2)が与えられたとき，線ABとACのy軸との交点の
## 座標値の符号が同じならFALSE，異なればTRUE(原点を含むか否か)
is.contain <- function(A){
  if(A[1] == FALSE) return(FALSE)          # y軸をまたがない判定されたとき用
  (intersept(A[c(1,2,3,4)]) * intersept(A[c(1,2,5,6)])) < 0
}

## 答え
triangles <- read.table("triangles.txt", sep=",")
ans <- 0
for(i in 1:1000){
  ans <- ans + is.contain(sort.apices(unlist(triangles[i, ])))
}
ans