どう書く過去問(第6回参考問題,F02)

E32の問題の（より簡単な）類題を以前解いていましたので投稿します。

まずF02の問題（2つの矩形に含まれるマス目の数）
問題はこちら->http://nabetani.sakura.ne.jp/hena/ordf02in2rec/
こちらの方が後で出題された問題ですがより簡単です。
Julia
最初二次元配列を0で埋めて、それぞれの矩形の部分は1ずつ足し、2となった部分を数えます。
「どう書く」の方々が一時間かける解き方ではありませんので、想定解ではないような。

```Julia
#Julia v 0.52,0.64

str="0 	5,1-7,9/3,2-8,6/0,5-9,5 	15
1 	0,0-9,9/0,0-9,9/0,0-9,9 	0
2 	0,0-9,9/0,0-0,9/1,0-9,9 	100
3 	2,5-7,6/0,5-7,7/2,0-8,6 	0
4 	1,9-4,9/4,9-7,9/0,3-7,4 	1
5 	6,1-6,9/5,0-7,4/5,1-7,2 	6
6 	4,0-9,8/5,1-6,8/0,2-9,7 	28
7 	2,8-8,9/7,9-8,9/8,3-8,9 	2
8 	3,3-9,4/0,1-8,4/1,2-8,9 	12
9 	2,1-8,3/0,1-3,7/8,3-8,4 	7
10 	5,4-6,9/0,0-6,0/5,3-9,8 	10
11 	1,1-9,7/1,1-3,8/3,8-7,9 	22
12 	2,4-6,7/3,2-7,8/1,0-9,4 	24
13 	0,2-1,5/8,1-8,3/1,8-6,8 	0
14 	5,2-9,5/9,1-9,2/8,0-8,6 	5
15 	5,0-6,4/2,1-6,4/3,8-3,9 	8
16 	0,4-6,9/4,1-6,9/7,6-9,7 	18
17 	0,0-5,5/0,1-2,8/5,3-9,4 	17
18 	0,2-5,6/5,6-8,7/0,1-2,6 	16
19 	7,2-8,4/1,0-6,8/1,3-7,6 	26
20 	4,3-9,3/0,0-6,5/0,0-4,8 	31
21 	3,4-4,6/2,2-4,8/2,0-8,4 	11
22 	1,2-6,5/0,5-4,7/2,8-2,9 	4
23 	4,1-7,5/2,1-9,9/1,7-2,9 	23
24 	1,6-5,6/0,3-5,7/0,2-2,6 	13
25 	1,3-3,4/1,4-3,4/9,2-9,9 	3
26 	6,3-7,6/2,2-2,3/1,3-9,8 	9
27 	2,2-9,7/1,8-9,8/2,2-8,9 	49
28 	1,2-6,9/7,6-9,9/4,3-9,9 	33
29 	6,0-7,5/0,4-3,8/1,4-5,8 	15
30 	2,0-9,7/0,5-3,8/5,1-7,7 	27
31 	1,2-8,7/3,1-4,3/2,3-5,8 	20
32 	1,0-7,7/0,1-5,4/0,0-2,3 	19
33 	2,0-3,7/1,1-3,7/5,3-5,9 	14
34 	7,2-9,8/1,0-6,8/0,2-9,9 	63
35 	1,1-5,3/0,3-8,7/2,3-8,7 	32
36 	3,4-6,6/1,0-9,1/4,0-9,9 	21
37 	0,0-4,7/0,5-5,9/0,2-4,5 	25
38 	1,1-9,9/2,2-7,4/2,4-7,7 	30
39 	3,2-9,9/2,0-6,6/0,5-8,9 	36
40 	0,1-8,8/0,5-9,8/2,3-2,4 	38
41 	0,0-8,6/4,3-9,9/7,1-9,9 	29
42 	0,0-8,8/2,4-9,8/0,1-9,2 	53"

fi=Array{Int}(10,10)

function calc(pos)
    x1,y1,x2,y2=pos[1:end]
    for i in x1:x2,j in y1:y2
        fi[i,j]=fi[i,j]+1
    end
end


function solve(s2)
    s3=split(s2,"/")
    for i in s3
        pos=[]
        s4=split(i,"-")

            for k in parse(Int,s4[1][1])+1:parse(Int,s4[2][1])+1
                for l in parse(Int,s4[1][3])+1:parse(Int,s4[2][3])+1
                    fi[k,l]+=1
                end
            end
    end
    sum=0
    for x in 1:10,y in 1:10
        if fi[x,y]==2
            sum+=1
        end
    end
    return sum
end

function main()
    str1=split(str,"\n")
    for s in str1
        fill!(fi,0)
        s1=split(s,"\t")
        ans=string(solve(s1[2]))
        if ans==strip(s1[3])
            sel="pass"
        else
            sel="fail"
        end
        print(sel," ",ans,"\n")
    end
end

main()
```

Prolog
計算で解くには、二つの矩形の重複部分の面積を足して、
三重になった部分の面積の三倍を引きます。
重複部分は、二つの図形のx座標、y座標をそれぞれリストに入れてソートし、
真ん中の二つずつを用いてできる長方形とします。(dup/3)
三重の部分は、二重の部分のひとつと、もう一つの矩形の重複部分として計算します。
P.S.
(問題をきちんと読まずコメントも読んでいませんでしたので、
百万X百万のデータを試していませんでしたが、すべてパスしましたので追加します。)

```Prolog
%swi-Prolog  version 7.4.2
%start.
%:-initialization(start).   % ideone

dup([],_,[]).
dup([X1-Y1,X2-Y2],[X3-Y3,X4-Y4],[]):-
     X2<X3;X4<X1;Y2<Y3;Y4<Y1.
dup([X1-Y1,X2-Y2],[X3-Y3,X4-Y4],F):-
     msort([Y3,Y1,Y2,Y4],[_,Y5,Y6,_]),msort([X1,X3,X4,X2],[_,X5,X6,_]),F=[X5-Y5,X6-Y6].

calc([],0).
calc([X1-Y1,X2-Y2],R):-R is (X2-X1+1)*(Y2-Y1+1).

solve([L1,L2,L3],R):-
     maplist(dup,[L1,L2,L3],[L2,L3,L1],L4),maplist(calc,L4,L5),foldl(plus,L5,0,Su),
     L4=[H|_],dup(H,L3,F),calc(F,V),R is Su-V*3,!.

start:-str(S),split_string(S,"\n\s","\s",L),pre(L).    %atom <-> string :souhoukou

pre([]).
pre([_,B,Q|T]):-
     atomics_to_string(L1,"/",B),maplist(split,L1,L2),
     maplist(mat,L2,L4),solve(L4,R),disp(R,Q),pre(T).

disp(R,A):-atom_number(A,N),(R=N->Str=" pass ";Str=" fail "),write(Str),writeln(R).

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

mat([A,B],R):-
     atomics_to_string(L1,",",A),atomics_to_string(L2,",",B),append(L1,L2,L3),
     maplist(atom_number,L3,[X1,Y1,X2,Y2]),R=[X1-Y1,X2-Y2].

str("0  5,1-7,9/3,2-8,6/0,5-9,5         15
1       0,0-9,9/0,0-9,9/0,0-9,9         0
2       0,0-9,9/0,0-0,9/1,0-9,9         100
3       2,5-7,6/0,5-7,7/2,0-8,6         0
4       1,9-4,9/4,9-7,9/0,3-7,4         1
5       6,1-6,9/5,0-7,4/5,1-7,2         6
6       4,0-9,8/5,1-6,8/0,2-9,7         28
7       2,8-8,9/7,9-8,9/8,3-8,9         2
8       3,3-9,4/0,1-8,4/1,2-8,9         12
9       2,1-8,3/0,1-3,7/8,3-8,4         7
10      5,4-6,9/0,0-6,0/5,3-9,8         10
11      1,1-9,7/1,1-3,8/3,8-7,9         22
12      2,4-6,7/3,2-7,8/1,0-9,4         24
13      0,2-1,5/8,1-8,3/1,8-6,8         0
14      5,2-9,5/9,1-9,2/8,0-8,6         5
15      5,0-6,4/2,1-6,4/3,8-3,9         8
16      0,4-6,9/4,1-6,9/7,6-9,7         18
17      0,0-5,5/0,1-2,8/5,3-9,4         17
18      0,2-5,6/5,6-8,7/0,1-2,6         16
19      7,2-8,4/1,0-6,8/1,3-7,6         26
20      4,3-9,3/0,0-6,5/0,0-4,8         31
21      3,4-4,6/2,2-4,8/2,0-8,4         11
22      1,2-6,5/0,5-4,7/2,8-2,9         4
23      4,1-7,5/2,1-9,9/1,7-2,9         23
24      1,6-5,6/0,3-5,7/0,2-2,6         13
25      1,3-3,4/1,4-3,4/9,2-9,9         3
26      6,3-7,6/2,2-2,3/1,3-9,8         9
27      2,2-9,7/1,8-9,8/2,2-8,9         49
28      1,2-6,9/7,6-9,9/4,3-9,9         33
29      6,0-7,5/0,4-3,8/1,4-5,8         15
30      2,0-9,7/0,5-3,8/5,1-7,7         27
31      1,2-8,7/3,1-4,3/2,3-5,8         20
32      1,0-7,7/0,1-5,4/0,0-2,3         19
33      2,0-3,7/1,1-3,7/5,3-5,9         14
34      7,2-9,8/1,0-6,8/0,2-9,9         63
35      1,1-5,3/0,3-8,7/2,3-8,7         32
36      3,4-6,6/1,0-9,1/4,0-9,9         21
37      0,0-4,7/0,5-5,9/0,2-4,5         25
38      1,1-9,9/2,2-7,4/2,4-7,7         30
39      3,2-9,9/2,0-6,6/0,5-8,9         36
40      0,1-8,8/0,5-9,8/2,3-2,4         38
41      0,0-8,6/4,3-9,9/7,1-9,9         29
42      0,0-8,8/2,4-9,8/0,1-9,2         53
0       0,0-999999,999999/0,0-999999,999999/0,0-999999,999999   0
1       0,0-999999,999999/0,0-0,999999/1,0-999999,999999        1000000000000
2       655822,899981-788586,907370/262080,47983-540321,834515/327083,392880-474728,550251      23235346312
3       332855,375381-953091,410430/311649,171289-637710,912139/113674,426911-658531,763493     120432128946
4       718118,613550-931221,983155/84495,98906-214393,787796/159096,14702-416478,360207        14449477996
5       809,351021-589370,525004/161241,390394-302773,958450/78299,230856-310951,941900         80430542457
6       140869,614312-559945,677721/424067,131309-645701,709237/22556,149538-902108,566473      101023697750
7       655941,129163-859649,985280/446717,159679-977047,839232/172790,559592-492587,741630     146781576755
8       17192,474077-715775,513703/177518,159867-395312,530025/331315,181585-695872,274046      14547945541
9       898603,252482-932681,923548/158284,561187-881317,881298/291114,46375-975112,431448      6099016393
10      460763,311625-742309,415024/708446,250395-980176,802067/190828,650489-798525,855977     17155773920
11      76405,197443-189085,423768/218793,635517-608524,914533/68011,184211-238902,819853       29209657076
12      602585,166640-862797,212028/844554,91101-971982,642729/130166,132319-619895,387625      1613805895
13      570213,345485-759193,657391/214801,517728-943628,936004/412700,32310-853707,623589      65618672419
14      251546,411491-781481,812128/271544,210234-536793,313835/174707,164436-353882,432689     10699927141
15      768602,340406-876104,451915/531084,97975-614595,607952/297417,452002-545499,950992      2248189616
16      824147,181473-928495,890221/673583,148595-734839,191460/532038,851156-892611,920296     2674653690
17      507676,577270-927426,825282/385783,352947-643538,691954/243369,815194-385405,859966     15581448155
18      388419,439549-745538,669102/262281,742072-609988,970128/533573,137288-596245,670546     14386837842
19      663239,518782-856702,589433/758115,84450-903932,642088/337647,24284-583025,565986       6965439376
20      191239,779501-419016,973110/461699,265809-619813,400896/295357,343268-995965,426583     9112009335
21      481413,405591-580708,502557/548827,255673-775012,641036/426629,627433-838039,929163     6168536238
22      9920,498487-514382,683023/226772,29017-628472,646705/311712,341208-824675,813994        86680486267
23      607788,403841-668184,518365/91263,688091-637506,857258/24319,559457-663076,919412       92407004992
24      77084,799236-139505,979891/754122,279472-794364,868062/150527,608666-281632,750541      0
25      169296,83569-620267,759983/460604,265256-945013,954017/317013,98311-745837,121044       85884450562
26      129661,44653-592189,297222/219053,537474-316753,980074/157470,756816-370610,907480      14720121165
27      297941,386287-716792,725006/241452,450763-567051,962750/195744,679475-346109,722435     74159512604
28      168144,237088-329400,634496/10381,564404-835828,912626/449243,161014-923398,676107      54486189445
29      107162,121311-807174,529239/344730,331975-894427,731597/581880,770044-619288,914307     91224212925
30      412012,102200-935128,257111/111516,225570-444846,539065/784025,129787-872324,570078     12278479070
31      800011,636792-837944,845950/7799,3048-945539,551037/197775,295503-609840,482184         76925305012
32      127131,26333-180762,397870/27576,261600-816030,833590/301519,411147-645517,557943       57806507475
33      32758,293294-988342,514135/468,543068-318854,548069/27211,318362-114542,567550  16448211254
34      100410,724118-597622,745585/183566,413277-751642,938721/672678,271783-953373,854704     43746337696
35      617281,172835-638934,558464/725936,550832-893293,968391/243005,644233-783866,774370     7539024478
36      306059,461338-761333,479832/59110,334011-979200,367681/201997,335634-587440,531481      17556869402
37      198441,770394-533721,965743/7845,436240-747623,621749/345710,713519-465402,866708       11528231295
38      856417,156222-995259,695178/552046,8773-879184,347237/114065,393927-827128,775960       4349052288
39      298522,174473-586813,447826/513017,410991-576739,639088/180342,283427-453079,776103     27756635628
40      676607,92015-788738,889720/351236,32426-799213,692704/334633,87130-927627,121184        76070680990
41      112863,136827-415321,945235/278661,676383-304033,860715/404074,160748-970146,761914     11439007625").
```

第六回参考問題（L-intersection）
問題はこちら->http://nabetani.sakura.ne.jp/hena/ord6lintersection/
Julia
図形は二個しかないのですが、L字型になったぶん複雑になっています。
二次元配列を0で満たし配列のそれぞれのL字図形のある部分に1を足し、2となった部分を数えます。
この問題で一番面倒だったのはL字図形を二個の矩形に分割するところでした。
一括処理する方法がわからず、向きによって場合分けしたのですが、
座標の値に1を足したり引いたりそのまま使ったりの判断を間違い、何回かやり直しました。


```Julia
# Version 0.5.2,0.64

#http://nabetani.sakura.ne.jp/hena/ord6lintersection/
str="#1 	23-94-28,89-06-51 	11
#2 	11-84-58,02-73-69 	40
#3 	18-41-86,77-04-32 	26
#4 	81-88-23,64-58-14 	0
#5 	31-29-07,41-87-69 	0
#6 	83-13-40,18-10-94 	1
#7 	77-80-92,21-72-38 	2
#8 	57-70-91,55-19-08 	3
#9 	18-22-75,66-80-91 	4
#10 	51-93-78,54-49-06 	5
#11 	58-70-96,17-43-76 	6
#12 	58-07-12,58-82-93 	7
#13 	41-29-07,35-95-88 	8
#14 	88-26-60,42-29-07 	9
#15 	18-40-85,34-40-91 	10
#16 	36-60-96,53-96-89 	11
#17 	51-39-02,44-98-69 	12
#18 	48-06-20,76-04-42 	13
#19 	85-29-18,26-50-93 	14
#20 	27-50-91,43-29-07 	15
#21 	57-06-20,48-60-91 	16
#22 	52-98-89,21-76-67 	17
#23 	67-12-40,45-80-92 	18
#24 	47-03-10,26-30-82 	19
#25 	74-28-06,21-86-37 	20
#26 	65-01-20,73-39-05 	21
#27 	17-72-86,36-50-94 	22
#28 	51-29-07,77-15-41 	23
#29 	33-98-39,82-16-02 	24
#30 	75-05-10,37-81-96 	25
#31 	72-58-06,48-80-96 	26
#32 	81-67-16,21-91-59 	27
#33 	13-96-57,24-96-79 	28
#34 	57-04-32,51-18-06 	29
#35 	88-03-52,28-41-86 	30
#36 	78-04-61,13-86-49 	31
#37 	58-12-20,27-50-85 	32
#38 	61-19-05,71-68-15 	33
#39 	63-29-16,18-31-83 	34
#40 	16-50-91,32-98-79 	35
#41 	82-17-03,38-40-81 	36
#42 	72-48-04,11-98-39 	37
#43 	77-05-10,28-50-62 	38
#44 	38-50-91,11-86-57 	39
#45 	87-05-10,13-97-69 	40
#46 	11-86-49,22-98-89 	44
#47 	11-97-69,12-86-67 	46
#48 	11-95-69,71-49-05 	47
#49 	28-31-92,13-98-79 	48"

fi=Array{Int}(10,10)

function calc(pos)
    x0,y0,x1,y1,x2,y2=pos[1:end]
    if x0<x1 && y0<y2 #x0<=x1でも良い
        for i in x0:x1,j in y0:y1
            fi[i,j]=fi[i,j]+1
        end
        for i in x0:x2,j in y1+1:y2
            fi[i,j]=fi[i,j]+1
        end
    elseif x0<=x1 && y0>y1
        for i in x0:x2,j in y2:y0
            fi[i,j]=fi[i,j]+1
        end
        for i in x0:x1,j in y1:y2-1
            fi[i,j]=fi[i,j]+1
        end
    elseif x0>=x1 && y0<y1
        for i in x1:x0,j in y0:y1
            fi[i,j]=fi[i,j]+1
        end
        for i in x2:x1-1,j in y0:y2
            fi[i,j]=fi[i,j]+1
        end
    else
        for i in x1:x0,j in y1:y0
            fi[i,j]=fi[i,j]+1
        end
        for i in x2:x0,j in y2:y1-1
            fi[i,j]=fi[i,j]+1
        end
    end
end

function solve(s2)
    s3=split(s2,",")
    for i in s3
        pos=[]
        s4=split(i,"-")
        for j in s4
            push!(pos,parse(Int,j[1])+1)
            push!(pos,parse(Int,j[2])+1)
        end
        calc(pos)
    end
    sum=0
    for x in 1:10,y in 1:10
        if fi[x,y]==2
            sum+=1
        end
    end
    return sum
end

function main()
    str1=split(str,"\n")
    for s in str1
        fill!(fi,0)
        s1=split(s,"\t")
#        s2=split(s1,",")
        ans=string(solve(s1[2]))
        if ans==strip(s1[3])
            sel="pass"
        else
            sel="fail"
        end
        print(sel," ",ans,"\n")
    end
end

main()

```

prolog
計算で解く方法はdivi/2で小さい長方形に分割して重複部分を足します。
重複部分は、二つの図形のx座標、y座標をそれぞれリストに入れてソートし、
真ん中の二つずつを用いてできる長方形とします。(dup/3)

```Prolog
%swi-Prolog  version 7.4.2
%start.
%:-initialization(start).   % ideone

divi([X1-Y1,X2-Y2,X3-Y3],[F1,F2]):-
     X1<X2,Y1<Y3,!,F1=[X1-Y1,X2-Y2],Y21 is Y2+1,F2=[X1-Y21,X3-Y3].
divi([X1-Y1,X2-Y2,X3-Y3],[F1,F2]):-
     X1=<X2,Y1>Y2,!,F1=[X1-Y2,X2-Y1],X21 is X2+1,F2=[X21-Y3,X3-Y1].
divi([X1-Y1,X2-Y2,X3-Y3],[F1,F2]):-
     X1>=X2,Y1<Y2,!,F1=[X2-Y1,X1-Y2],X21 is X2-1,F2=[X3-Y1,X21-Y3].
divi([X1-Y1,X2-Y2,X3-Y3],[F1,F2]):-
     X1>X2,Y1>Y3,F1=[X2-Y2,X1-Y1],Y21 is Y2-1,F2=[X3-Y3,X1-Y21].

dup([X1-Y1,X2-Y2],[X3-Y3,X4-Y4],[]):-
     X2<X3;X4<X1;Y2<Y3;Y4<Y1.
dup([X1-Y1,X2-Y2],[X3-Y3,X4-Y4],F):-
     msort([Y3,Y1,Y2,Y4],[_,Y5,Y6,_]),msort([X1,X3,X4,X2],[_,X5,X6,_]),F=[X5-Y5,X6-Y6].

calc([],0).
calc([X1-Y1,X2-Y2],R):-R is (X2-X1+1)*(Y2-Y1+1).

dupl([],_,[]).
dupl([H|T],[F1,F2],L):-dupl(T,[F1,F2],L1),dup(H,F1,F3),dup(H,F2,F4),L=[F4,F3|L1].

solve(L1,L2,R):-
     divi(L1,L11),divi(L2,L22),dupl(L11,L22,L3),maplist(calc,L3,L4),foldl(plus,L4,0,R),!.

     
start:-str(S),split_string(S,"\n\s","\s",L),pre(L).    %atom <-> string :souhoukou

pre([]).
pre([_,B,Q|T]):-
     atomics_to_string(L1,",",B),maplist(split,L1,[L2,L3]),maplist(mat,L2,L4),
     maplist(mat,L3,L5),solve(L4,L5,R),disp(R,Q),pre(T).

disp(R,A):-atom_number(A,N),(R=N->Str=" pass ";Str=" fail "),write(Str),writeln(R).

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

mat(A,B):-atom_chars(A,L),maplist(atom_number,L,[X,Y]),B=X-Y.

str("#1      23-94-28,89-06-51       11
#2      11-84-58,02-73-69       40
#3      18-41-86,77-04-32       26
#4      81-88-23,64-58-14       0
#5      31-29-07,41-87-69       0
#6      83-13-40,18-10-94       1
#7      77-80-92,21-72-38       2
#8      57-70-91,55-19-08       3
#9      18-22-75,66-80-91       4
#10     51-93-78,54-49-06       5
#11     58-70-96,17-43-76       6
#12     58-07-12,58-82-93       7
#13     41-29-07,35-95-88       8
#14     88-26-60,42-29-07       9
#15     18-40-85,34-40-91       10
#16     36-60-96,53-96-89       11
#17     51-39-02,44-98-69       12
#18     48-06-20,76-04-42       13
#19     85-29-18,26-50-93       14
#20     27-50-91,43-29-07       15
#21     57-06-20,48-60-91       16
#22     52-98-89,21-76-67       17
#23     67-12-40,45-80-92       18
#24     47-03-10,26-30-82       19
#25     74-28-06,21-86-37       20
#26     65-01-20,73-39-05       21
#27     17-72-86,36-50-94       22
#28     51-29-07,77-15-41       23
#29     33-98-39,82-16-02       24
#30     75-05-10,37-81-96       25
#31     72-58-06,48-80-96       26
#32     81-67-16,21-91-59       27
#33     13-96-57,24-96-79       28
#34     57-04-32,51-18-06       29
#35     88-03-52,28-41-86       30
#36     78-04-61,13-86-49       31
#37     58-12-20,27-50-85       32
#38     61-19-05,71-68-15       33
#39     63-29-16,18-31-83       34
#40     16-50-91,32-98-79       35
#41     82-17-03,38-40-81       36
#42     72-48-04,11-98-39       37
#43     77-05-10,28-50-62       38
#44     38-50-91,11-86-57       39
#45     87-05-10,13-97-69       40
#46     11-86-49,22-98-89       44
#47     11-97-69,12-86-67       46
#48     11-95-69,71-49-05       47
#49     28-31-92,13-98-79       48").
```
2019.5.1追加
F02の問題のcielavenirさんのコメントに
「座標圧縮、いもす法です..元の問題だと矩形の個数が2000個です、私の答案だと耐えられます。」
と知らないアルゴリズムがありましたので、調べる前に推測してプログラムを作ってみようと思い、
一応元のプログラムよりは大きい数、多数のデータに使えそうなのができましたので投稿します。
すべての矩形のx座標とy座標を(下辺と右辺の座標に1を足し)順位（lx,lyのインデックス）
に変換して二次元配列を作り、碁盤のように座標間にマス（縮尺を変えた矩形）が入るイメージです。
元の矩形の座標から配列の該当する升を見つけ１を足していきます。
次に配列の値が2の部分をもとの縮尺に戻し面積を計算し足していきます。
テストケースは小さい値もパスしていますが、大きい値のみ乗せています。
ただ2000個の矩形の問題のテストケースが手に入りませんので、
2000個の矩形で解けるか不明ですし、解けても時間は結構かかりそうです。

```Julia
#Julia version 0.52,0.64

str="0 	0,0-999999,999999/0,0-999999,999999/0,0-999999,999999 	0
1 	0,0-999999,999999/0,0-0,999999/1,0-999999,999999 	1000000000000
2 	655822,899981-788586,907370/262080,47983-540321,834515/327083,392880-474728,550251 	23235346312
3 	332855,375381-953091,410430/311649,171289-637710,912139/113674,426911-658531,763493 	120432128946
4 	718118,613550-931221,983155/84495,98906-214393,787796/159096,14702-416478,360207 	14449477996
5 	809,351021-589370,525004/161241,390394-302773,958450/78299,230856-310951,941900 	80430542457
6 	140869,614312-559945,677721/424067,131309-645701,709237/22556,149538-902108,566473 	101023697750
7 	655941,129163-859649,985280/446717,159679-977047,839232/172790,559592-492587,741630 	146781576755
8 	17192,474077-715775,513703/177518,159867-395312,530025/331315,181585-695872,274046 	14547945541
9 	898603,252482-932681,923548/158284,561187-881317,881298/291114,46375-975112,431448 	6099016393
10 	460763,311625-742309,415024/708446,250395-980176,802067/190828,650489-798525,855977 	17155773920
11 	76405,197443-189085,423768/218793,635517-608524,914533/68011,184211-238902,819853 	29209657076
12 	602585,166640-862797,212028/844554,91101-971982,642729/130166,132319-619895,387625 	1613805895
13 	570213,345485-759193,657391/214801,517728-943628,936004/412700,32310-853707,623589 	65618672419
14 	251546,411491-781481,812128/271544,210234-536793,313835/174707,164436-353882,432689 	10699927141
15 	768602,340406-876104,451915/531084,97975-614595,607952/297417,452002-545499,950992 	2248189616
16 	824147,181473-928495,890221/673583,148595-734839,191460/532038,851156-892611,920296 	2674653690
17 	507676,577270-927426,825282/385783,352947-643538,691954/243369,815194-385405,859966 	15581448155
18 	388419,439549-745538,669102/262281,742072-609988,970128/533573,137288-596245,670546 	14386837842
19 	663239,518782-856702,589433/758115,84450-903932,642088/337647,24284-583025,565986 	6965439376
20 	191239,779501-419016,973110/461699,265809-619813,400896/295357,343268-995965,426583 	9112009335
21 	481413,405591-580708,502557/548827,255673-775012,641036/426629,627433-838039,929163 	6168536238
22 	9920,498487-514382,683023/226772,29017-628472,646705/311712,341208-824675,813994 	86680486267
23 	607788,403841-668184,518365/91263,688091-637506,857258/24319,559457-663076,919412 	92407004992
24 	77084,799236-139505,979891/754122,279472-794364,868062/150527,608666-281632,750541 	0
25 	169296,83569-620267,759983/460604,265256-945013,954017/317013,98311-745837,121044 	85884450562
26 	129661,44653-592189,297222/219053,537474-316753,980074/157470,756816-370610,907480 	14720121165
27 	297941,386287-716792,725006/241452,450763-567051,962750/195744,679475-346109,722435 	74159512604
28 	168144,237088-329400,634496/10381,564404-835828,912626/449243,161014-923398,676107 	54486189445
29 	107162,121311-807174,529239/344730,331975-894427,731597/581880,770044-619288,914307 	91224212925
30 	412012,102200-935128,257111/111516,225570-444846,539065/784025,129787-872324,570078 	12278479070
31 	800011,636792-837944,845950/7799,3048-945539,551037/197775,295503-609840,482184 	76925305012
32 	127131,26333-180762,397870/27576,261600-816030,833590/301519,411147-645517,557943 	57806507475
33 	32758,293294-988342,514135/468,543068-318854,548069/27211,318362-114542,567550 	16448211254
34 	100410,724118-597622,745585/183566,413277-751642,938721/672678,271783-953373,854704 	43746337696
35 	617281,172835-638934,558464/725936,550832-893293,968391/243005,644233-783866,774370 	7539024478
36 	306059,461338-761333,479832/59110,334011-979200,367681/201997,335634-587440,531481 	17556869402
37 	198441,770394-533721,965743/7845,436240-747623,621749/345710,713519-465402,866708 	11528231295
38 	856417,156222-995259,695178/552046,8773-879184,347237/114065,393927-827128,775960 	4349052288
39 	298522,174473-586813,447826/513017,410991-576739,639088/180342,283427-453079,776103 	27756635628
40 	676607,92015-788738,889720/351236,32426-799213,692704/334633,87130-927627,121184 	76070680990
41 	112863,136827-415321,945235/278661,676383-304033,860715/404074,160748-970146,761914 	11439007625"

function solve(s2)
    lx,ly=[],[]
    s3=split(s2,"/")
    s4=map(x->split(x,"-"),s3)
    s5=map(x->map(y->split(y,","),x),s4)
    s6=map(x->map(y->map(z->parse(Int,z),y),x),s5)
    for i in s6
       push!(lx,i[1][1])
       push!(lx,i[2][1]+1)
       push!(ly,i[1][2])
       push!(ly,i[2][2]+1)
    end
    sort!(lx)
    sort!(ly)
    nx=length(lx)
    ny=length(ly)
    fi=Array{Int}(nx,ny)
    fill!(fi,0)
    #辞書にしたらより速い？
    for i in s6
       for k in findfirst(x->x==i[1][1],lx):findfirst(x->x==i[2][1]+1,lx)-1,
           l in findfirst(y->y==i[1][2],ly):findfirst(y->y==i[2][2]+1,ly)-1
                fi[k,l]+=1
       end
    end
    sum=0
    for x in 1:nx,y in 1:ny
        if fi[x,y]==2
           sum+=(lx[x+1]-lx[x])*(ly[y+1]-ly[y])
        end
    end
    return sum
end

function main()
    str1=split(str,"\n")
    for s in str1
        s1=split(s,"\t")
        ans=string(solve(s1[2]))
        if ans==strip(s1[3])
            sel="pass"
        else
            sel="fail"
        end
        print(sel," ",ans,"\n")
    end
end

main()
```
まだ計算量が多そうでしたので、計算量をもっと減らせないか考えました。
左上から積算した矩形の上辺と下辺の差と左辺と右辺の差で
重なり具合が求められるのではないかと思いいろいろ試行しましたが、
上下あるいは左右のどちらかで良く、上のプログラムと同様に二次元配列を作り、
座標の間のマスの状態を矩形の上辺の種類
（n個のの矩形に入る線、矩形から出る線,それ以外）によってn,-n,0とします。
そして上にマスがあるときはその状態の数字を加えます。
そして状態が2のときに縮尺をもとに戻した矩形の面積を加えていきます。
やはり2000個の矩形で正解が出るか、実行時間はどうかはわかりません。

```Prolog
% SWI-Prolog (threaded, 32 bits, version 7.4.2)
%start.
%:-initialization(start).　　%ideone

twoar(_,0,_).      % two dimension array
twoar(F,X,Y):-arg(X,F,V),functor(V,y,Y),X1 is X-1,twoar(F,X1,Y).
data(F,X,Y,V):-arg(X,F,V1),arg(Y,V1,V).

lx([X1-_,X2-_],[X1,X2]).
ly([_-Y1,_-Y2],[Y1,Y2]).

dup(_,I,_,LX,_,_,R,R):-length(LX,I).
dup(F,I,J,LX,LY,L,N,R):-
     I1 is I-1,(I1>0->data(F,I1,J,V1);V1=0), nth1(I,LX,X),nth1(J,LY,Y),
     findall(X,(member([X-Y1,_-Y2],L),Y1=<Y,Y<Y2),L3),length(L3,V5),
     findall(X,(member([_-Y1,X-Y2],L),Y1=<Y,Y<Y2),L4),length(L4,V6),
     VX is V1+V5-V6,data(F,I,J,VX),J2 is J+1,I2 is I+1,
     (VX=:=2->(nth1(J2,LY,Y3),nth1(I2,LX,X3),N1 is N+(Y3-Y)*(X3-X));N1=N),
     (length(LY,J2)->dup(F,I2,1,LX,LY,L,N1,R);dup(F,I,J2,LX,LY,L,N1,R)).

solve(L,R):-
     maplist(lx,L,L1),maplist(ly,L,L2),flatten(L1,L3),flatten(L2,L4),
     sort(L3,LX),sort(L4,LY),length(LX,N1),length(LY,N2),
     functor(F,x,N1),twoar(F,N1,N2),dup(F,1,1,LX,LY,L,0,R),!.

start:-str(S),split_string(S,"\n\s","\s",L),pre(L).    %atom <-> string :souhoukou

pre([]).
pre([_,B,Q|T]):-
     atomics_to_string(L1,"/",B),maplist(split,L1,L2),
     maplist(mat,L2,L4),solve(L4,R),disp(R,Q),pre(T).

disp(R,A):-atom_number(A,N),(R=N->Str=" pass ";Str=" fail "),write(Str),writeln(R).

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

mat([A,B],R):-
     atomics_to_string(L1,",",A),atomics_to_string(L2,",",B),append(L1,L2,L3),
     maplist(atom_number,L3,[X1,Y1,X2,Y2]),X3 is X2+1,Y3 is Y2+1,R=[X1-Y1,X3-Y3].

%
str("0       0,0-999999,999999/0,0-999999,999999/0,0-999999,999999   0
1       0,0-999999,999999/0,0-0,999999/1,0-999999,999999        1000000000000
2       655822,899981-788586,907370/262080,47983-540321,834515/327083,392880-474728,550251      23235346312
3       332855,375381-953091,410430/311649,171289-637710,912139/113674,426911-658531,763493     120432128946
4       718118,613550-931221,983155/84495,98906-214393,787796/159096,14702-416478,360207        14449477996
5       809,351021-589370,525004/161241,390394-302773,958450/78299,230856-310951,941900         80430542457
6       140869,614312-559945,677721/424067,131309-645701,709237/22556,149538-902108,566473      101023697750
7       655941,129163-859649,985280/446717,159679-977047,839232/172790,559592-492587,741630     146781576755
8       17192,474077-715775,513703/177518,159867-395312,530025/331315,181585-695872,274046      14547945541
9       898603,252482-932681,923548/158284,561187-881317,881298/291114,46375-975112,431448      6099016393
10      460763,311625-742309,415024/708446,250395-980176,802067/190828,650489-798525,855977     17155773920
11      76405,197443-189085,423768/218793,635517-608524,914533/68011,184211-238902,819853       29209657076
12      602585,166640-862797,212028/844554,91101-971982,642729/130166,132319-619895,387625      1613805895
13      570213,345485-759193,657391/214801,517728-943628,936004/412700,32310-853707,623589      65618672419
14      251546,411491-781481,812128/271544,210234-536793,313835/174707,164436-353882,432689     10699927141
15      768602,340406-876104,451915/531084,97975-614595,607952/297417,452002-545499,950992      2248189616
16      824147,181473-928495,890221/673583,148595-734839,191460/532038,851156-892611,920296     2674653690
17      507676,577270-927426,825282/385783,352947-643538,691954/243369,815194-385405,859966     15581448155
18      388419,439549-745538,669102/262281,742072-609988,970128/533573,137288-596245,670546     14386837842
19      663239,518782-856702,589433/758115,84450-903932,642088/337647,24284-583025,565986       6965439376
20      191239,779501-419016,973110/461699,265809-619813,400896/295357,343268-995965,426583     9112009335
21      481413,405591-580708,502557/548827,255673-775012,641036/426629,627433-838039,929163     6168536238
22      9920,498487-514382,683023/226772,29017-628472,646705/311712,341208-824675,813994        86680486267
23      607788,403841-668184,518365/91263,688091-637506,857258/24319,559457-663076,919412       92407004992
24      77084,799236-139505,979891/754122,279472-794364,868062/150527,608666-281632,750541      0
25      169296,83569-620267,759983/460604,265256-945013,954017/317013,98311-745837,121044       85884450562
26      129661,44653-592189,297222/219053,537474-316753,980074/157470,756816-370610,907480      14720121165
27      297941,386287-716792,725006/241452,450763-567051,962750/195744,679475-346109,722435     74159512604
28      168144,237088-329400,634496/10381,564404-835828,912626/449243,161014-923398,676107      54486189445
29      107162,121311-807174,529239/344730,331975-894427,731597/581880,770044-619288,914307     91224212925
30      412012,102200-935128,257111/111516,225570-444846,539065/784025,129787-872324,570078     12278479070
31      800011,636792-837944,845950/7799,3048-945539,551037/197775,295503-609840,482184         76925305012
32      127131,26333-180762,397870/27576,261600-816030,833590/301519,411147-645517,557943       57806507475
33      32758,293294-988342,514135/468,543068-318854,548069/27211,318362-114542,567550  16448211254
34      100410,724118-597622,745585/183566,413277-751642,938721/672678,271783-953373,854704     43746337696
35      617281,172835-638934,558464/725936,550832-893293,968391/243005,644233-783866,774370     7539024478
36      306059,461338-761333,479832/59110,334011-979200,367681/201997,335634-587440,531481      17556869402
37      198441,770394-533721,965743/7845,436240-747623,621749/345710,713519-465402,866708       11528231295
38      856417,156222-995259,695178/552046,8773-879184,347237/114065,393927-827128,775960       4349052288
39      298522,174473-586813,447826/513017,410991-576739,639088/180342,283427-453079,776103     27756635628
40      676607,92015-788738,889720/351236,32426-799213,692704/334633,87130-927627,121184        76070680990
41      112863,136827-415321,945235/278661,676383-304033,860715/404074,160748-970146,761914     11439007625").
```
もう少し、n個の矩形の~~計算量がO(n*2),せめてO(n^2)~~
計算量がO(n)、せめて繰り返しが(2*n)^2でなくn^2回のアルゴリズムがないか考え、
思いつけば投稿し、思いつかなければ、座標圧縮やいもす法を調べるつもりです。
2019.5.2追加。
二次元配列を使う代わりに、
同じy座標の頂点や辺のx座標をyのタグをつけた同じリストに収納し(lxy)、
二次元配列のx座標の代わりにする方法です。
dupにおける繰り返しは減りますが、その代わり前処理が増えますし,
抜本的な改良にはならないようです。

```Prolog
% SWI-Prolog (threaded, 32 bits, version 7.4.2)

ly([_-Y1,_-Y2],[Y1:[],Y2:[]]).

lxy([],R,R).
lxy([[X1-Y1,X2-Y2]|T],R1,R):-
     lxy([X1-Y1,X2-Y2],R1,[],R2),lxy(T,R2,R).

lxy([X1-Y1,X2-Y2],[Y:L|T],R1,R):-
     Y<Y1,!,lxy([X1-Y1,X2-Y2],T,[Y:L|R1],R).
lxy([X1-Y1,X2-Y2],[Y:L|T],R1,R):-
     Y<Y2,!,append(L,[X1:1,X2:(-1)],L1),lxy([X1-Y1,X2-Y2],T,[Y:L1|R1],R).
lxy(_,YL,R1,R):-
     reverse(R1,R2),append(R2,YL,R).

dup([_],R,R).
dup([Y1,Y2|T1],R1,R):-
     dup(Y1,Y2,0,0,R2),R3 is R1+R2,dup([Y2|T1],R3,R).

dup(_:[],_,_,_,0).
dup(_:[_],_,_,R,R).
dup(Y1:[X1:N1,X2:N2|T],Y2:_,S,R1,R):-
     S1 is S+N1,(S1=:=2->R2 is R1+(X2-X1)*(Y2-Y1);R2=R1),
     dup(Y1:[X2:N2|T],Y2:_,S1,R2,R).

mysort(X:L,X:R):-msort(L,R).

solve(L,R):-
     maplist(ly,L,L2),flatten(L2,L4) ,
     sort(L4,LY),lxy(L,LY,XY),maplist(mysort,XY,XY1),dup(XY1,0,R),!.
```
2019.5.6追加
上のプログラムでネックになっているのは、矩形の座標から配列の座標を求めるところのようです。
そこでJuliaでその部分に辞書を使いましたところ、
他の部分は最後のプログラムのリストに収納するところを、一つ前のプログラムのように二次元配列に追加するようにしたぐらいで、基本的な計算量やアルゴリズムは変わりませんが、
結構早くなりましたので投稿します。

```Julia
function solve(s6)
    lx,ly=[],[]
    for i in s6
       push!(lx,i[1][1])
       push!(lx,i[2][1]+1)
       push!(ly,i[1][2])
       push!(ly,i[2][2]+1)
    end
    sort!(lx)
    sort!(ly)
    nx=length(lx)
    ny=length(ly)
    dlx=Dict()
    dly=Dict()
    for i in 1:nx
       dlx[lx[i]]=i
   end
   for i in 1:ny
       dly[ly[i]]=i
   end
    fi=Array{Int}(nx,ny)
    fill!(fi,0)
      for i in s6
      for k in dlx[i[1][1]]:dlx[i[2][1]+1]-1
         fi[k,dly[i[1][2]]]+=1
         fi[k,dly[i[2][2]+1]]-=1
       end
     end
    sum=0
   for x in 1:nx,y in 1:ny
      if x>1 && y>1
          fi[x,y]+=fi[x,y-1]
      elseif y>1
          fi[x,y]+=fi[x,y-1]
      end
      if fi[x,y]==2
         sum+=(lx[x+1]-lx[x])*(ly[y+1]-ly[y])
      end
   end
   return sum
end

function main()
    str1=split(str,"\n")
    for s in str1
        s1=split(s,"\t")
        s3=split(s1[2],"/")
        s4=map(x->split(x,"-"),s3)
        s5=map(x->map(y->split(y,","),x),s4)
        s6=map(x->map(y->map(z->parse(Int,z),y),x),s5)
        ans=string(solve(s6))
        if ans==strip(s1[3])
            sel="pass"
        else
            sel="fail"
        end
        print(sel," ",ans,"\n")
    end
end

dat=[]
for i in 1:2000
    push!(dat,[[i*2,i*2],[i*2+10000,i*2+10000]])
end
println(solve(dat))
```