Here are some pictures courtesy of Doug Jones at AT&T (click for fullsize):
Here are the three final test problems along with the solutions that the winning program (Yalta) came up with. A note on the three problems I chose for the final testing: 1) NAME="sliver" TESTARGS="0 1 1 99" (just a tiny sliver) "sliver" takes a long thin slice off the upper left of the square. I wanted one problem that would have a fairly small area to test the ability of programs to cut the square into a bunch of equally sized pieces - and I didn't want to use the "obvious" tiny triangle in the corner. 2) NAME="midway" TESTARGS="1 80 98 20" (almost through the middle) The obvious thing to do would be to have an initial cut that went exactly through the center - thus making a score of "zero" possible fairly easily. But I figured that some folks would check that case and treat it specially. While this would be completely legal, I decided that a line that "almost" passed through the middle would be more challenging. 3) NAME="950" TESTARGS="62 100 100 50" (area = 950 units) Other interesting cases arise when the area of the first piece is an even fraction (1/3, 1/4, ..., 1/12) of the 10000 units. In these cases, a score of zero should be possible. Perhaps I should have rewarded those folks who checked for these cases ... but I didn't. But this is a chunk somewhere between 1/10 and 1/11 of the total area. Specifically - an area of 950 units. Name of final: sliver midway 950 Score on final: 275 7 23 Total pieces: 42 22 22 Largest piece: 277.241 458.643 475.103 Smallest piece: 1.359 451.062 451.719 Time of run: 569.01 569.02 569.07 Starting Line: 0 1 1 99 1 80 98 20 62 100 100 50 output: 16 1 18 90 20 92 1 22 87 49 61 80 output: 33 26 34 61 13 38 34 88 98 23 62 64 output: 51 73 49 6 8 13 47 88 25 93 99 11 output: 66 13 68 94 13 10 62 94 35 71 92 9 output: 83 19 84 86 62 77 27 20 3 96 82 10 output: 22 17 90 16 49 41 76 85 15 73 79 2 output: 16 34 60 33 87 90 49 25 48 24 5 73 output: 85 49 6 51 91 85 68 41 4 61 35 24 output: 31 67 76 66 90 69 73 29 31 8 3 45 output: 70 83 0 84 97 70 85 27 12 15 63 62 ====================
======================= Your run on sliver ran for 569.01 seconds. Score on sliver is 275 based on 42 pieces from 10 lines. The starting line for sliver was:0 1 1 99 Your output was: 16 1 18 90 33 26 34 61 51 73 49 6 66 13 68 94 83 19 84 86 22 17 90 16 16 34 60 33 85 49 6 51 31 67 76 66 70 83 0 84 Scorer courtesy of Chad Hurwitz. Areas and coordinates below are shown as rounded to one decimal but all calculations are double precsion. 276.1=(18.2,100.0)(1.0,100.0)(0.8,84.0)(17.9,83.7) 14.9=(1.0,100.0)(0.0,100.0)(0.0,84.0)(0.8,84.0) 274.3=(82.7,0.0)(100.0,0.0)(100.0,15.9)(83.0,16.1) 275.7=(35.1,100.0)(18.2,100.0)(17.9,83.7)(34.6,83.5) 277.1=(51.8,100.0)(35.1,100.0)(34.6,83.5)(51.3,83.3) 276.1=(68.1,100.0)(51.8,100.0)(51.3,83.3)(67.7,83.0) 275.8=(84.2,100.0)(68.1,100.0)(67.7,83.0)(84.0,82.8) 276.8=(0.0,1.0)(0.0,0.0)(16.0,0.0)(16.4,17.1)(0.2,17.3) 1.4=(0.0,1.0)(0.2,17.3)(0.0,17.3) 275.6=(100.0,100.0)(84.2,100.0)(84.0,82.8)(100.0,82.6) 277.0=(16.0,0.0)(32.3,0.0)(32.7,16.8)(16.4,17.1) 277.1=(32.3,0.0)(48.8,0.0)(49.3,16.6)(32.7,16.8) 277.0=(48.8,0.0)(65.7,0.0)(66.1,16.4)(49.3,16.6) 275.2=(65.7,0.0)(82.7,0.0)(83.0,16.1)(66.1,16.4) 276.6=(0.2,17.3)(16.4,17.1)(16.7,34.0)(0.3,34.4) 4.3=(0.0,17.3)(0.2,17.3)(0.3,34.4)(0.0,34.4) 276.6=(16.4,17.1)(32.7,16.8)(33.2,33.6)(16.7,34.0) 277.1=(32.7,16.8)(49.3,16.6)(49.8,33.2)(33.2,33.6) 277.2=(49.3,16.6)(66.1,16.4)(66.5,32.9)(49.8,33.2) 276.1=(66.1,16.4)(83.0,16.1)(83.2,32.5)(66.5,32.9) 275.9=(83.0,16.1)(100.0,15.9)(100.0,32.1)(83.2,32.5) 276.7=(0.3,34.4)(16.7,34.0)(17.1,50.7)(0.5,51.1) 7.2=(0.0,34.4)(0.3,34.4)(0.5,51.1)(0.0,51.2) 276.4=(16.7,34.0)(33.2,33.6)(33.7,50.3)(17.1,50.7) 277.0=(33.2,33.6)(49.8,33.2)(50.3,49.9)(33.7,50.3) 276.7=(49.8,33.2)(66.5,32.9)(66.9,49.5)(50.3,49.9) 276.0=(66.5,32.9)(83.2,32.5)(83.4,49.0)(66.9,49.5) 276.0=(83.2,32.5)(100.0,32.1)(100.0,48.6)(83.4,49.0) 276.8=(0.5,51.1)(17.1,50.7)(17.5,67.3)(0.7,67.7) 9.9=(0.0,51.2)(0.5,51.1)(0.7,67.7)(0.0,67.7) 276.3=(17.1,50.7)(33.7,50.3)(34.2,66.9)(17.5,67.3) 277.1=(33.7,50.3)(50.3,49.9)(50.8,66.6)(34.2,66.9) 276.7=(50.3,49.9)(66.9,49.5)(67.3,66.2)(50.8,66.6) 276.2=(66.9,49.5)(83.4,49.0)(83.7,65.8)(67.3,66.2) 276.3=(83.4,49.0)(100.0,48.6)(100.0,65.5)(83.7,65.8) 277.1=(0.7,67.7)(17.5,67.3)(17.9,83.7)(0.8,84.0) 12.5=(0.0,67.7)(0.7,67.7)(0.8,84.0)(0.0,84.0) 276.4=(17.5,67.3)(34.2,66.9)(34.6,83.5)(17.9,83.7) 277.2=(34.2,66.9)(50.8,66.6)(51.3,83.3)(34.6,83.5) 276.3=(50.8,66.6)(67.3,66.2)(67.7,83.0)(51.3,83.3) 275.7=(67.3,66.2)(83.7,65.8)(84.0,82.8)(67.7,83.0) 275.6=(83.7,65.8)(100.0,65.5)(100.0,82.6)(84.0,82.8) Largest Area: 277.24177882 Smallest Area: 1.35927364 Yalta SCORE: 275 42 10 569.01 ======================= Your run on midway ran for 569.02 seconds. Score on midway is 7 based on 22 pieces from 10 lines. The starting line for midway was:1 80 98 20 Your output was: 20 92 1 22 13 38 34 88 8 13 47 88 13 10 62 94 62 77 27 20 49 41 76 85 87 90 49 25 91 85 68 41 90 69 73 29 97 70 85 27 Scorer courtesy of Chad Hurwitz. Areas and coordinates below are shown as rounded to one decimal but all calculations are double precsion. 451.6=(24.5,65.4)(0.0,7.0)(0.0,0.0)(1.2,0.0)(32.7,60.4) 457.2=(100.0,18.8)(100.0,80.8)(85.2,27.9) 451.1=(0.0,80.6)(0.0,18.3)(14.5,71.7) 454.5=(0.0,100.0)(0.0,80.6)(14.5,71.7)(22.2,100.0) 451.2=(14.5,71.7)(0.0,18.3)(0.0,7.0)(24.5,65.4) 457.7=(22.2,100.0)(14.5,71.7)(24.5,65.4)(39.0,100.0) 452.6=(100.0,0.0)(100.0,18.8)(85.2,27.9)(77.5,0.0) 458.0=(39.0,100.0)(24.5,65.4)(32.7,60.4)(53.2,100.0) 457.3=(53.2,100.0)(32.7,60.4)(39.8,56.0)(65.5,100.0) 452.1=(32.7,60.4)(1.2,0.0)(7.2,0.0)(39.8,56.0) 457.1=(65.5,100.0)(39.8,56.0)(46.5,51.8)(76.1,100.0) 451.7=(39.8,56.0)(7.2,0.0)(14.7,0.0)(46.5,51.8) 456.5=(76.1,100.0)(46.5,51.8)(53.1,47.7)(85.2,100.0) 453.7=(46.5,51.8)(14.7,0.0)(23.8,0.0)(53.1,47.7) 458.0=(85.2,100.0)(53.1,47.7)(59.9,43.6)(92.8,100.0) 451.3=(53.1,47.7)(23.8,0.0)(34.4,-0.0)(59.9,43.6) 457.7=(92.8,100.0)(59.9,43.6)(67.0,39.2)(98.8,100.0) 451.2=(59.9,43.6)(34.4,-0.0)(46.6,-0.0)(67.0,39.2) 458.6=(100.0,100.0)(98.8,100.0)(67.0,39.2)(75.2,34.1)(100.0,92.5) 451.5=(67.0,39.2)(46.6,-0.0)(60.7,0.0)(75.2,34.1) 458.4=(100.0,92.5)(75.2,34.1)(85.2,27.9)(100.0,80.8) 451.1=(75.2,34.1)(60.7,0.0)(77.5,0.0)(85.2,27.9) Largest Area: 458.64311575 Smallest Area: 451.06260682 Yalta SCORE: 7 22 10 569.02 ======================= Your run on 950 ran for 569.07 seconds. Score on 950 is 23 based on 22 pieces from 10 lines. The starting line for 950 was:62 100 100 50 Your output was: 87 49 61 80 98 23 62 64 25 93 99 11 35 71 92 9 3 96 82 10 15 73 79 2 48 24 5 73 4 61 35 24 31 8 3 45 12 15 63 62 Scorer courtesy of Chad Hurwitz. Areas and coordinates below are shown as rounded to one decimal but all calculations are double precsion. 452.5=(91.2,0.0)(100.0,0.0)(100.0,0.3)(52.3,52.2)(47.4,47.6) 475.1=(100.0,100.0)(62.0,100.0)(79.4,77.1)(100.0,96.1) 452.0=(100.0,33.5)(100.0,50.0)(79.4,77.1)(70.4,68.8) 451.8=(100.0,20.7)(100.0,33.5)(70.4,68.8)(63.4,62.4) 452.0=(100.0,9.9)(100.0,20.7)(63.4,62.4)(57.5,57.0) 453.1=(100.0,0.3)(100.0,9.9)(57.5,57.0)(52.3,52.2) 455.3=(0.0,0.0)(37.1,0.0)(20.1,22.4)(0.0,3.9) 452.1=(80.8,0.0)(91.2,0.0)(47.4,47.6)(42.2,42.8) 451.7=(69.1,0.0)(80.8,0.0)(42.2,42.8)(36.3,37.4) 453.2=(55.1,0.0)(69.1,0.0)(36.3,37.4)(29.2,30.9) 453.2=(37.1,0.0)(55.1,0.0)(29.2,30.9)(20.1,22.4) 452.2=(8.3,100.0)(0.0,100.0)(0.0,99.3)(47.4,47.6)(52.3,52.2) 474.9=(100.0,50.0)(100.0,96.1)(79.4,77.1) 452.5=(62.0,100.0)(44.2,100.0)(70.4,68.8)(79.4,77.1) 452.9=(44.2,100.0)(30.4,100.0)(63.4,62.4)(70.4,68.8) 452.4=(30.4,100.0)(18.7,100.0)(57.5,57.0)(63.4,62.4) 452.6=(18.7,100.0)(8.3,100.0)(52.3,52.2)(57.5,57.0) 451.9=(0.0,49.0)(0.0,3.9)(20.1,22.4) 452.1=(0.0,99.3)(0.0,89.6)(42.2,42.8)(47.4,47.6) 452.4=(0.0,89.6)(0.0,78.7)(36.3,37.4)(42.2,42.8) 451.9=(0.0,78.7)(0.0,65.8)(29.2,30.9)(36.3,37.4) 451.9=(0.0,65.8)(0.0,49.0)(20.1,22.4)(29.2,30.9) Largest Area: 475.10301805 Smallest Area: 451.71876330 Yalta SCORE: 23 22 10 569.07