三角形と点の関係

締め切りが 11/18 10:00AM なので，その 1 分後に投稿するように予約する

想定時間「10分」だと...いつもながら，大幅に超過したわ。

三角形と点の関係

【概要】

三角形と点があります。
三角形と点の位置関係は、下表のいずれかになります：

記号     説明
A     点は、三角形の内側にあります。
B     点は、三角形の辺上にありますが、頂点上ではありません。
C     点は、三角形の頂点にあります。
D     点は、三角形の外側にあります。

どの関係になるのかを求めるプログラムを書いて下さい。

【入出力】

入力は
(1,1)(10,1)(1,10)/(2,2) (1,2)(1,1)(2,1)/(12,34) (1,3)(3,1)(4,4)/(2,2)
こんな感じです。

三角形と点の組が空白区切りで並んでいます。
スラッシュの前が三角形です。() 内に、頂点のx座標y座標がコンマ区切りで並んでいます。スラッシュの後は点の座標です。

出力は、各組が前述の A〜D のどれに該当するのかを区切り文字なしで並べたものです。

先程の例だと

    最初の組(1,1)(10,1)(1,10)/(2,2)の関係は、A。
    二番目の組(1,2)(1,1)(2,1)/(12,34)の関係は、D。
    最後の組(1,3)(3,1)(4,4)/(2,2)の関係は、B。

ということで、ADBを出力すれば正解となります。
末尾の改行はあってもなくても構いません。

【例】
入力     出力
(1,1)(10,1)(1,10)/(2,2) (1,2)(1,1)(2,1)/(12,34) (1,3)(3,1)(4,4)/(2,2)     ADB
(10,200)(10,10)(123,10)/(4,5) (12,35)(31,12)(41,44)/(41,44)     DC

【補足】

    座標は、いずれも正の整数で、百万を超えることはありません。
    ひとつの入力に含まれる 三角形-点 の組は 10以下です。
    いずれの三角形も、ゼロより大きな面積を持ちます。
    不正な入力に対処する必要はありません。


点 (a, b, c) の面積と，(a, b, z), (b, c, z), (c, a, z) の面積を求め，後三者の面積の和と前者の面積の関係でやろうかなと思ったけど，テストデータが意地悪（座標値がでかい）なので，別の，プリミティブな方法で書いた（かったるい）

slope = function(x1, y1, x2, y2) (y2 - y1)/(x2 - x1)

decomp = function(s) { # 入力行の分解
    t = unlist(strsplit(s, " "))
    sapply(t, function(u) {
        w = gsub("\\(", "", gsub(")", ",", sub("/", "", u)))
        as.numeric(unlist(strsplit(w, ",")))
    })
}

disc = function(p) { # 位置関係の判定
    x = p[1:3 * 2 - 1]
    y = p[1:3 * 2]
    o = order(x)
    x = c(x[o], p[7])
    y = c(y[o], p[8])
    a.x = x[1]
    a.y = y[1]
    b.x = x[2]
    b.y = y[2]
    c.x = x[3]
    c.y = y[3]
    z.x = x[4]
    z.y = y[4]
    eq.x = c(a.x, b.x, c.x) %in% z.x
    eq.y = c(a.y, b.y, c.y) %in% z.y
    if (any(eq.x & eq.y))
        ans = "C"
    else if (sum(eq.x) == 2 || sum(eq.y) == 2) {
        ans = "B"
    } else if (min(x) >= z.x || z.x >= max(x) || min(y) >= z.y || z.y >= max(y)) {
        ans = "D"
    } else if (z.x >= a.x && b.x >= z.x) {
        slope.az = slope(a.x, a.y, z.x, z.y)
        slope.ab = slope(a.x, a.y, b.x, b.y)
        slope.ac = slope(a.x, a.y, c.x, c.y)
        if (slope.az == slope.ab || slope.az == slope.ac) {
            ans = "B"
        } else if (slope.az > max(slope.ab, slope.ac) || slope.az < min(slope.ab, slope.ac)) {
            ans = "D"
        } else ans = "A"
    } else if (z.x > b.x && c.x >= z.x) {
        slope.cz = slope(c.x, c.y, z.x, z.y)
        slope.ca = slope(c.x, c.y, a.x, a.y)
        slope.cb = slope(c.x, c.y, b.x, b.y)
        if (slope.cz == slope.ca || slope.cz == slope.cb) {
            ans = "B"
        } else if (slope.cz > max(slope.ca, slope.cb) || slope.cz < min(slope.ca, slope.cb)) {
            ans = "D"
        } else ans = "A"
    } else ans = "x"
    ans
}

f = function(s) {
    p = decomp(s) # 入力行の分解 >> 4 点の x, y 座標を要素数 8 の列ベクトルにする行列
    cat(paste(apply(p, 2, disc), collapse = "")) # 位置関係の判定
}

f("(1,1)(10,1)(1,10)/(2,2) (1,2)(1,1)(2,1)/(12,34) (1,3)(3,1)(4,4)/(2,2)") # ADB

f("(10,200)(10,10)(123,10)/(4,5) (12,35)(31,12)(41,44)/(41,44)") # DC

f("(16,13)(1,11)(13,18)/(12,16) (2,16)(2,5)(17,10)/(8,7) (11,18)(4,4)(16,15)/(6,6) (5,9)(1,15)(6,13)/(9,18) (12,18)(7,12)(16,10)/(14,9) (6,18)(12,5)(8,12)/(6,18) (18,11)(18,6)(5,6)/(18,10) (8,2)(19,14)(5,11)/(8,2)") # ABADDCBC

f("(6,2)(26,15)(39,25)/(9,37) (46,39)(29,40)(49,1)/(39,27) (7,15)(13,47)(30,36)/(10,31) (1,31)(6,43)(25,37)/(25,37) (16,43)(31,16)(35,44)/(23,34) (49,36)(26,14)(4,1)/(9,15) (7,45)(41,13)(31,33)/(33,29)") # DABCADB

f("(63944,492389)(380462,882527)(496266,305904)/(63944,492389) (399396,945126)(3461,410781)(770003,22887)/(161835,624519) (11251,380400)(389242,357769)(685090,412104)/(460477,401536) (810430,271880)(924670,512828)(308863,176996)/(810430,271880)") # CBBC

f("(622671,535852)(364079,448665)(10452,792969)/(364079,448665) (41,20)(57,9)(79,50)/(52,28) (368208,870739)(996210,589804)(649917,745441)/(577542,777094) (38,60)(18,16)(31,78)/(27,40) (77,20)(54,83)(9,12)/(42,59) (279707,902871)(849496,790389)(763927,751666)/(570239,812148) (946989,831217)(602996,336137)(34367,168235)/(34367,168235)") # CABAABC

f("(178948,265045)(931263,891839)(781020,277145)/(329466,268070) (338,475)(663,835)(259,960)/(317,642) (289859,521270)(664758,949028)(854363,96377)/(478027,379639) (960,678)(185,953)(968,166)/(766,687) (481,661)(941,606)(424,399)/(505,539) (894179,443799)(722784,445061)(290417,278627)/(894179,443799) (796185,261874)(373280,282588)(13608,764317)/(13608,764317)") # BABAACC

f("(433423,181160)(832013,121400)(359517,786345)/(473282,175184) (485,8690)(4722,1849)(7785,8488)/(6430,7329) (818475,458807)(839588,892108)(379565,202673)/(818475,458807) (131839,712754)(48808,955181)(506046,158685)/(506046,158685) (8435,3330)(7171,7896)(8676,9365)/(8146,7191) (9937,4933)(3373,1020)(4835,9395)/(6082,7342) (358973,847370)(876921,331437)(247831,429607)/(436558,400156)") # BACCAAB

f("(62493,977407)(518706,994645)(299775,962634)/(366635,988899) (94459,94078)(97847,48616)(46433,75423)/(94597,79113) (828610,187056)(832354,79565)(95750,759545)/(279901,589550) (95604,54883)(67680,26554)(45312,90675)/(69873,36818) (807133,92093)(71884,217935)(554759,810479)/(71884,217935) (83067,73903)(92600,11864)(23347,94602)/(65277,73576) (140792,148212)(203528,414277)(11301,473993)/(140792,148212)") # BABACAC

f("(158839,197999)(608294,629979)(117450,803952)/(132343,724233) (16656,583111)(421768,921769)(751443,911561)/(16656,583111) (913703,284010)(698577,8906)(349662,568541)/(913703,284010) (355069,187114)(879282,384550)(537733,854548)/(575674,616336) (34536,772021)(760160,148154)(361255,817079)/(441036,683294) (439610,950121)(646821,369587)(138285,752935)/(390271,860139) (393398,255982)(711129,576840)(355440,876162)/(671608,610098)") # ACCABAB

f("(159635,876685)(888617,781119)(480723,957682)/(480723,957682) (93588,685668)(64882,993088)(162406,77103)/(106678,600523) (780162,833747)(757864,76945)(435151,731142)/(593723,736001) (434282,643984)(445591,676783)(753853,60119)/(753853,60119) (275601,291635)(778880,26144)(97423,935493)/(584178,285958) (961646,450205)(291968,836498)(87569,238183)/(207861,466806) (820255,200270)(644706,594803)(520996,202782)/(626434,319571)") # CBACBAA

f("(688483,858004)(835886,244022)(553322,192384)/(835886,244022) (51419,482928)(514395,53297)(344931,940813)/(387297,718934) (721856,686900)(856884,522826)(314664,338075)/(392124,364468) (579199,994594)(97241,936422)(502551,112180)/(330592,596296) (812841,538190)(845697,938354)(122714,149293)/(122714,149293) (105757,293420)(534586,548742)(597299,773659)/(501583,662648) (599633,724163)(694400,337219)(92480,632980)/(548438,710269)") # CBBACAA

f("(892402,565227)(480608,382305)(818167,303522)/(783524,181393) (972526,151377)(225533,281022)(270554,240711)/(255547,254148) (948978,580225)(22448,737666)(299192,435497)/(391440,334774) (623398,895656)(827192,867194)(727880,126074)/(723742,95194) (761473,966845)(349291,914983)(193691,32011)/(271491,473497) (581768,864305)(802761,210568)(224151,90772)/(706326,190602) (481556,71688)(511498,710360)(181945,471407)/(72094,391756) (210710,232479)(337274,561336)(449777,309744)/(606788,360489) (396169,793629)(680416,666213)(418241,127653)/(575546,450789) (959550,369216)(998967,880416)(154188,493257)/(422642,451910)") # DBDDBBDDBB

f("(461484,305711)(435830,117953)(582877,502129)/(536509,427104) (21441,229521)(73349,117583)(587578,949623)/(391160,631812) (351400,100879)(426425,222272)(203246,620105)/(397768,175904) (192849,99802)(707078,931842)(985751,877379)/(510660,614031) (485816,377542)(476282,467118)(794093,981347)/(672700,784929) (494245,336449)(297827,18638)(544752,124606)/(419220,215056) (162698,379593)(237723,500986)(827620,763861)/(209066,454618) (634932,955311)(120703,123271)(351149,515585)/(438514,637500) (149490,780650)(70083,25940)(116451,100965)/(98740,72308) (459254,720823)(377165,233374)(348508,187006)/(366219,215663)") # AAADADDADA