|
|
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
====================
The following are the polygons created and their areas
for each of the solutions that "Yalta" came up with:
=======================
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
|
