Closest-pair problem: Difference between revisions
m
→{{header|Phix}}: added syntax colouring, made p2js compatible
m (→{{header|REXX}}: added whitespace.) |
m (→{{header|Phix}}: added syntax colouring, made p2js compatible) |
||
Line 3,291:
=={{header|Phix}}==
Brute force and divide and conquer (translated from pseudocode) approaches compared
<!--<lang Phix>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">bruteForceClosestPair</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y1</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y2</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">dx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x1</span><span style="color: #0000FF;">-</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dy</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">y1</span><span style="color: #0000FF;">-</span><span style="color: #000000;">y2</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">mind</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dx</span><span style="color: #0000FF;">*</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">+</span><span style="color: #000000;">dy</span><span style="color: #0000FF;">*</span><span style="color: #000000;">dy</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">minp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y1</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y2</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">dx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x1</span><span style="color: #0000FF;">-</span><span style="color: #000000;">x2</span>
<span style="color: #000000;">dx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dx</span><span style="color: #0000FF;">*</span><span style="color: #000000;">dx</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">dx</span><span style="color: #0000FF;"><</span><span style="color: #000000;">mind</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">dy</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">y1</span><span style="color: #0000FF;">-</span><span style="color: #000000;">y2</span>
<span style="color: #000000;">dx</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">dy</span><span style="color: #0000FF;">*</span><span style="color: #000000;">dy</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">dx</span><span style="color: #0000FF;"><</span><span style="color: #000000;">mind</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">mind</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dx</span>
<span style="color: #000000;">minp</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">sqrt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mind</span><span style="color: #0000FF;">),</span><span style="color: #000000;">minp</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">testset</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_rnd</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">({</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span><span style="color: #000000;">10000</span><span style="color: #0000FF;">))</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #0000FF;">{</span><span style="color: #004080;">atom</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">points</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">bruteForceClosestPair</span><span style="color: #0000FF;">(</span><span style="color: #000000;">testset</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- (Sorting the final point pair makes brute/dc more likely to tally. Note however
-- when >1 equidistant pairs exist, brute and dc may well return different pairs;
-- it is only a problem if they decide to return different minimum distances.)</span>
<span style="color: #004080;">atom</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y2</span><span style="color: #0000FF;">}}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">points</span><span style="color: #0000FF;">))</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Closest pair: {%f,%f} {%f,%f}, distance=%f (%3.2fs)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">X</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">Y</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">xP</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">testset</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">byY</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">compare</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">[</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">],</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">[</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">yP</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">custom_sort</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">routine_id</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"byY"</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">testset</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">distsq</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y1</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y2</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p2</span>
<span style="color: #000000;">x1</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">x2</span>
<span style="color: #000000;">y1</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">y2</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">x1</span><span style="color: #0000FF;">*</span><span style="color: #000000;">x1</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">y1</span><span style="color: #0000FF;">*</span><span style="color: #000000;">y1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">closestPair</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">xP</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">yP</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- where xP is P(1) .. P(N) sorted by x coordinate, and
-- yP is P(1) .. P(N) sorted by y coordinate (ascending order)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">N</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">xP</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">midN</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">N</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">yP</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">N</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">N</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">3</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">bruteForceClosestPair</span><span style="color: #0000FF;">(</span><span style="color: #000000;">xP</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">xL</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">xP</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">midN</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">xR</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">xP</span><span style="color: #0000FF;">[</span><span style="color: #000000;">midN</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">N</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">yL</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span>
<span style="color: #000000;">yR</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">xm</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">xP</span><span style="color: #0000FF;">[</span><span style="color: #000000;">midN</span><span style="color: #0000FF;">][</span><span style="color: #000000;">X</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">N</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">yP</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">X</span><span style="color: #0000FF;">]<=</span><span style="color: #000000;">xm</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">yL</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">yL</span><span style="color: #0000FF;">,</span><span style="color: #000000;">yP</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">yR</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">yR</span><span style="color: #0000FF;">,</span><span style="color: #000000;">yP</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">{</span><span style="color: #004080;">atom</span> <span style="color: #000000;">dL</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">pairL</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">closestPair</span><span style="color: #0000FF;">(</span><span style="color: #000000;">xL</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">yL</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{</span><span style="color: #004080;">atom</span> <span style="color: #000000;">dR</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">pairR</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">closestPair</span><span style="color: #0000FF;">(</span><span style="color: #000000;">xR</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">yR</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{</span><span style="color: #004080;">atom</span> <span style="color: #000000;">dmin</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">pairMin</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">({</span><span style="color: #000000;">dL</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pairL</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">dR</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pairR</span><span style="color: #0000FF;">})</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">yS</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">yP</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">xm</span><span style="color: #0000FF;">-</span><span style="color: #000000;">yP</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">X</span><span style="color: #0000FF;">])<</span><span style="color: #000000;">dmin</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">yS</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">yS</span><span style="color: #0000FF;">,</span><span style="color: #000000;">yP</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">nS</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">yS</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{</span><span style="color: #004080;">atom</span> <span style="color: #000000;">closest</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">cPair</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">dmin</span><span style="color: #0000FF;">*</span><span style="color: #000000;">dmin</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pairMin</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">nS</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">k</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">nS</span> <span style="color: #008080;">and</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">yS</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">][</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">yS</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">])<</span><span style="color: #000000;">dmin</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">distsq</span><span style="color: #0000FF;">(</span><span style="color: #000000;">yS</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">],</span><span style="color: #000000;">yS</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">d</span><span style="color: #0000FF;"><</span><span style="color: #000000;">closest</span> <span style="color: #008080;">then</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">closest</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cPair</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">yS</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">yS</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]}}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">k</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">sqrt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">closest</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">cPair</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #000000;">points</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">closestPair</span><span style="color: #0000FF;">(</span><span style="color: #000000;">xP</span><span style="color: #0000FF;">,</span><span style="color: #000000;">yP</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y2</span><span style="color: #0000FF;">}}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">points</span><span style="color: #0000FF;">))</span> <span style="color: #000080;font-style:italic;">-- (see note above)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Closest pair: {%f,%f} {%f,%f}, distance=%f (%3.2fs)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">})</span>
<!--</lang>-->
{{out}}
<pre>
|