blob: 33f06a61da7b02841930c61255327ee7bae86874 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
|
(defun read-segs (name)
(mapcar (do match `@x0,@y0 -> @x1,@y1` @1
(list (tofloat x0) (tofloat y0) (tofloat x1) (tofloat y1)))
(file-get-lines name)))
(defun read-int-segs (name)
(mapcar (do match `@x0,@y0 -> @x1,@y1` @1
(list (toint x0) (toint y0) (toint x1) (toint y1)))
(file-get-lines name)))
(defun ccw-from (x0 y0 x1 y1 x2 y2)
(let ((dx1 (- x1 x0))
(dy1 (- y1 y0))
(dx2 (- x2 x0))
(dy2 (- y2 y0)))
(> (* dx1 dy2) (* dx2 dy1))))
(defun intersect (ax0 ay0 ax1 ay1 bx0 by0 bx1 by1)
(and (neq (ccw-from ax0 ay0 ax1 ay1 bx0 by0)
(ccw-from ax0 ay0 ax1 ay1 bx1 by1))
(neq (ccw-from bx0 by0 bx1 by1 ax0 ay0)
(ccw-from bx0 by0 bx1 by1 ax1 ay1))))
(defun b-proj-a (ax0 ay0 ax1 ay1 bx by)
(let* ((adx (- ax1 ax0))
(ady (- ay1 ay0))
(bdx (- bx ax0))
(bdy (- by ay0))
(a*b (+ (* adx bdx) (* ady bdy)))
(a*a (+ (* adx adx) (* ady ady)))
(b/a (/ a*b a*a)))
(list (+ ax0 (* b/a adx))
(+ ay0 (* b/a ady)))))
(defun isecpoint (ax0 ay0 ax1 ay1 bx0 by0 bx1 by1)
(tree-bind (x0 y0) (b-proj-a ax0 ay0 ax1 ay1 bx0 by0)
(tree-bind (x1 y1) (b-proj-a ax0 ay0 ax1 ay1 bx1 by1)
(list (+ x0 (/ (- x1 x0) 2))
(+ y0 (/ (- y1 y0) 2))))))
(defun collinear (ax0 ay0 ax1 ay1 bx0 by0 bx1 by1)
(and (not (ccw-from ax0 ay0 ax1 ay1 bx0 by0))
(not (ccw-from ax0 ay0 ax1 ay1 bx1 by1))
(not (ccw-from bx0 by0 bx1 by1 ax0 ay0))
(not (ccw-from bx0 by0 bx1 by1 ax1 ay1))
(and (or (<= ax0 bx0 ax1) (>= ax0 bx0 ax1)
(<= bx0 ax0 bx1) (>= bx0 ax0 bx1)))
(and (or (<= ay0 by0 ay1) (>= ay0 by0 ay1)
(<= by0 ay0 by1) (>= by0 ay0 by1)))))
(defun dist (x0 y0 x1 y1)
(sqrt (+ (square (- x1 x0)) (square (- y1 y0)))))
(defun lap-length (ax0 ay0 ax1 ay1 bx0 by0 bx1 by1)
(let ((a0-between (or (and (<= bx0 ax0 bx1) (<= by0 ay0 by1))
(and (>= bx0 ax0 bx1) (>= by0 ay0 by1))))
(a1-between (or (and (<= bx0 ax1 bx1) (<= by0 ay1 by1))
(and (>= bx0 ax1 bx1) (>= by0 ay1 by1))))
(b0-between (or (and (<= ax0 bx0 ax1) (<= ay0 by0 ay1))
(and (>= ax0 bx0 ax1) (>= ay0 by0 ay1))))
(b1-between (or (and (<= ax0 bx1 ax1) (<= ay0 by1 ay1))
(and (>= ax0 bx1 ax1) (>= ay0 by1 ay1)))))
(cond
((and a0-between a1-between) (dist ax0 ay0 ax1 ay1))
((and b0-between b1-between) (dist bx0 by0 bx1 by1))
(a0-between (if b0-between
(dist bx0 by0 ax0 ay0)
(dist bx1 by1 ax0 ay0)))
(t (if b0-between
(dist bx0 by0 ax1 ay1)
(dist bx0 by0 ax1 ay1))))))
(defun clip (ax0 ay0 ax1 ay1 bx0 by0 bx1 by1)
(let ((a0-between (or (and (<= bx0 ax0 bx1) (<= by0 ay0 by1))
(and (>= bx0 ax0 bx1) (>= by0 ay0 by1))))
(a1-between (or (and (<= bx0 ax1 bx1) (<= by0 ay1 by1))
(and (>= bx0 ax1 bx1) (>= by0 ay1 by1))))
(b0-between (or (and (<= ax0 bx0 ax1) (<= ay0 by0 ay1))
(and (>= ax0 bx0 ax1) (>= ay0 by0 ay1))))
(b1-between (or (and (<= ax0 bx1 ax1) (<= ay0 by1 ay1))
(and (>= ax0 bx1 ax1) (>= ay0 by1 ay1)))))
(assert (or a0-between a1-between b0-between b1-between)
"clip: problem with ~s" (list ax0 ay0 ax1 ay1 bx0 by0 bx1 by1))
(cond
((and a0-between a1-between) (list ax0 ay0 ax1 ay1))
((and b0-between b1-between) (list bx0 by0 bx1 by1))
(a0-between (if b0-between
(list bx0 by0 ax0 ay0)
(list bx1 by1 ax0 ay0)))
(t (if b0-between
(list bx0 by0 ax1 ay1)
(list bx0 by0 ax1 ay1))))))
(defun unify (ax0 ay0 ax1 ay1 bx0 by0 bx1 by1)
(let ((a0-between (or (and (<= bx0 ax0 bx1) (<= by0 ay0 by1))
(and (>= bx0 ax0 bx1) (>= by0 ay0 by1))))
(a1-between (or (and (<= bx0 ax1 bx1) (<= by0 ay1 by1))
(and (>= bx0 ax1 bx1) (>= by0 ay1 by1))))
(b0-between (or (and (<= ax0 bx0 ax1) (<= ay0 by0 ay1))
(and (>= ax0 bx0 ax1) (>= ay0 by0 ay1))))
(b1-between (or (and (<= ax0 bx1 ax1) (<= ay0 by1 ay1))
(and (>= ax0 bx1 ax1) (>= ay0 by1 ay1)))))
(cond
((and a0-between a1-between) (list bx0 by0 bx1 by1))
((and b0-between b1-between) (list ax0 ay0 ax1 ay1))
(a0-between (if b0-between
(list bx0 by0 ax1 ay1)
(list bx0 by0 ax1 ay1)))
(t (if b0-between
(list bx1 by1 ax0 ay0)
(list bx0 by0 ax0 ay0))))))
(defun rectilinear (x0 y0 x1 y1)
(or (= x0 x1) (= y0 y1)))
(defun point-on-segment (x0 y0 x1 y1 px py)
(and (or (<= x0 px x1) (<= x1 px x0))
(or (<= y0 py y1) (<= y1 py y0))
(not (ccw-from x0 y0 x1 y1 px py))
(not (ccw-from x1 y1 x0 y0 px py))))
(defun solve-1 (segs)
(let (isegs points)
(each-match (((@ax0 @ay0 @ax1 @ay1)
(@bx0 @by0 @bx1 @by1))
(comb segs 2))
(when (and (rectilinear ax0 ay0 ax1 ay1)
(rectilinear bx0 by0 bx1 by1))
(cond
((collinear ax0 ay0 ax1 ay1 bx0 by0 bx1 by1)
(push (clip ax0 ay0 ax1 ay1 bx0 by0 bx1 by1) isegs))
((intersect ax0 ay0 ax1 ay1 bx0 by0 bx1 by1)
(push (isecpoint ax0 ay0 ax1 ay1 bx0 by0 bx1 by1) points)))))
(prinl ^(len points 0 ,(len points)))
(upd points uniq)
(prinl ^(len points 1 ,(len points)))
(set points (append-matches (@(as p (@px @py)) points)
(block nil
(each-match ((@x0 @y0 @x1 @y1) isegs)
(if (point-on-segment x0 y0 x1 y1 px py)
(return)))
(list p))))
(prinl ^(len points 2 ,(len points)))
(prinl isegs)
(let ((nl (len isegs))
(l 0))
(while (neq nl l)
(let (nsegs pairs (count 0))
(set l nl)
(each-match ((@(as l0 (@ax0 @ay0 @ax1 @ay1))
@(as l1 (@bx0 @by0 @bx1 @by1)))
(comb isegs 2))
(cond
((collinear ax0 ay0 ax1 ay1 bx0 by0 bx1 by1)
(push (list l0 l1) pairs))))
(each-match ((@(as l0 (@ax0 @ay0 @ax1 @ay1))
@(as l1 (@bx0 @by0 @bx1 @by1)))
pairs)
(if (and (member l0 isegs)
(member l1 isegs))
(upd isegs (opip (remq l0)
(remq l1)
(push (unify ax0 ay0 ax1 ay1 bx0 by0 bx1 by1))))))
(set nl (len isegs)))))
(prinl isegs)
(prinl (len isegs))
(+ (len points)
(len isegs)
[sum isegs (lambda-match
(((@x0 @y0 @x1 @y1)) (dist x0 y0 x1 y1)))])))
(defun easy-solve-1 (segs)
(let ((ph (hash)))
(each-match ((@x0 @y0 @x1 @y1) segs)
(cond
((eql x0 x1)
(each ((y (range y0 y1)))
(inc [ph (list x0 y) 0])))
((eql y0 y1)
(each ((x (range x0 x1)))
(inc [ph (list x y0) 0])))))
[count-if (op < 1) ph cdr]))
(defun easy-solve-2 (segs)
(let ((ph (hash)))
(each-match ((@x0 @y0 @x1 @y1) segs)
(cond
((eql x0 x1)
(each ((y (range y0 y1)))
(inc [ph (list x0 y) 0])))
((eql y0 y1)
(each ((x (range x0 x1)))
(inc [ph (list x y0) 0])))
((eql (abs (- x1 x0)) (abs (- y1 y0)))
(each ((x (range x0 x1))
(y (range y0 y1)))
(inc [ph (list x y) 0])))))
[count-if (op < 1) ph cdr]))
|
