CodeIQ:三角形と点の関係の解答

@nabetaniさんのCodeIQの問題です。
問題とテストケースはこちらのお世話になりました。解答もあります。
->https://blog.goo.ne.jp/r-de-r/e/5c073909a51e47fed4b9bb0222eccf12
出題者のhttps://nabetani.hatenablog.com/に
次の問題「共通部分は何角形？」の準備のための問題
とありますが、「共通部分は何角形？」は、テストケースが見つかりませんでしたので
解いていませんので、この解法が役に立つかどうか不明です。

三組の線分について点が端点か->線上にあるか->上または下にあるかの順に考え、
三点の上下にそれそれ一つ以上線分があれば三角形の内部として解きました。(sol44/3)
三頂点はsolv44/2でX座標でソートし、sol44/3のnth1/4で二頂点の組み合わせを作りました。
直線の式はY=(Y2-Y1)/(X2-X1)\*(X-X1)+Y1ですが、
小数にならないようにP1 is (Y-Y1)*(X2-X1),P2 is (Y2-Y1)\*(X-X1)とし、
P1とP2の大小で直線と点の上下を判断しました。 (che44/4)
垂直の場合はX2-X1が零になるので別に処理しました。
F=(Y1-Y)*(Y2-Y)はYがY1とY2の間か外か重なるかを判断しています。 (che44/4)

```Prolog
%swi-prolog v7.4.2,7.6.4
%:-initialization(start44).   %ideone
%start44.
 
chec44(L,R):-
     member(0,L)->R='C';(member(1,L)->R='B';(subset([2,3],L)->R='A';R='D')).

che44((X1,Y1),(X2,Y2),(X,Y),R):-
     X2=:=X1,!,(X=\=X1->R=10;(F=(Y1-Y)*(Y2-Y),(F=:=0->R=0;(F<0->R=1;R=10)))).
che44((X1,Y1),(X2,Y2),(X,Y),R):-
     (X1-X)*(X2-X)>0->R=10;(P1 is (Y-Y1)*(X2-X1),P2 is (Y2-Y1)*(X-X1),
     (P2=:=P1->((X1=:=X;X2=:=X)->R=0;R=1);(P1>P2->R=2;R=3))).

arr44([],[]).
arr44([X,Y|T],R):-
     arr44(T,R1),atom_chars(X,L),delete(L,'(',L1),concat_atom(L1,X1),
     atom_chars(Y,L2),delete(L2,')',L3),concat_atom(L3,Y1),
     atom_number(X1,X2),atom_number(Y1,Y2),R=[(X2,Y2)|R1].

sol44(L,(X,Y),R):-　　　　　% L=[(X1,Y1),(X2,Y2),(X3,Y3)]　
     findall(A,(between(1,3,K),nth1(K,L,_,[V,V1]),che44(V,V1,(X,Y),A)),R1),chec44(R1,R).

solv44([],[]).
solv44([H|T],R):-
     solv44(T,R1),H=[X,Y],atomics_to_string(X1,',',X),arr44(X1,L),
     atomics_to_string(Y1,',',Y),arr44(Y1,[Y2]),
     sort(L,LX),sol44(LX,Y2,R2),R=[R2|R1].

start44:-
     f44(S,Q),((atomics_to_string(L,"\s",S),maplist(split,L,L1),solv44(L1,R1),
     atomics_to_string(R1,R))->disp44(R,Q);writeln(fail)),fail.
start44.

split(S,L):-atomics_to_string(L,"/",S).

disp44(R,Q):-(R==Q->Str="good ";Str=" bad "),write(" "),write(Str),writeln(R).

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

f44("(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").

f44("(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").

f44("(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").

f44("(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").

f44("(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").

f44("(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").

f44("(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").

f44("(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").

f44("(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").

f44("(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").

f44("(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").

f44("(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").

```
別解
三辺それぞれの対角の点と入力された点がすべて辺の同じ側にあることを
条件とする解き方です。
辺を作る二点と対角の点の組み合わせはsol44/3のnth1/4で作っています。
上記のP1,P2のほかに対角の点でP3,P4を作り(P2-P1)*(P4-P3)の0,正、負と
求める点が辺上、求める点と対角の点が同側、反対側が対応します。
三辺で調べて、最初に外部の場合を決定、その他すべて正なら内部、
0が二つなら頂点、のこりが辺上です。

```Prolog
%:-initialization(start44).   %ideone
%start44.
 
chec44(L,R):-
     (member(10,L)->R='D';(delete(L,1,[])->R='A';(delete(L,0,[_])->R='C';R='B'))).

che44((X1,Y1),(X2,Y2),(X3,Y3),(X,Y),R):-
     X2=:=X1,!,F=(X-X1)*(X3-X1),(F=:=0->R=0;(F>0->R=1;R=10)).
che44((X1,Y1),(X2,Y2),(X3,Y3),(X,Y),R):-
     P1 is (Y-Y1)*(X2-X1),P2 is (Y2-Y1)*(X-X1),
     P3 is (Y3-Y1)*(X2-X1),P4 is (Y2-Y1)*(X3-X1),F=(P2-P1)*(P4-P3),(F=:=0->R=0;(F>0->R=1;R=10)).

arr44([],[]).
arr44([X,Y|T],R):-
     arr44(T,R1),atom_chars(X,L),delete(L,'(',L1),concat_atom(L1,X1),
     atom_chars(Y,L2),delete(L2,')',L3),concat_atom(L3,Y1),
     atom_number(X1,X2),atom_number(Y1,Y2),R=[(X2,Y2)|R1].

sol44(L,(X,Y),R):-　　　　　% L=[(X1,Y1),(X2,Y2),(X3,Y3)]　
     findall(A,(between(1,3,K),nth1(K,L,V3,[V1,V2]),che44(V1,V2,V3,(X,Y),A)),R1),chec44(R1,R).

solv44([],[]).
solv44([H|T],R):-
     solv44(T,R1),H=[X,Y],atomics_to_string(X1,',',X),arr44(X1,L),
     atomics_to_string(Y1,',',Y),arr44(Y1,[Y2]),
     sort(L,LX),sol44(LX,Y2,R2),R=[R2|R1].

start44:-
     f44(S,Q),((atomics_to_string(L,"\s",S),maplist(split,L,L1),solv44(L1,R1),
     atomics_to_string(R1,R))->disp44(R,Q);writeln(fail)),fail.
start44.

split(S,L):-atomics_to_string(L,"/",S).

disp44(R,Q):-(R==Q->Str="good ";Str=" bad "),write(" "),write(Str),writeln(R).
```