## 819 - Gifts Large and Small

Moderator: Board moderators

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

### 819 - Gifts Large and Small

Can anyone provide some critical example?

If the input polygon is not convex, we can consider packing its convex hull, right?
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
If the input polygon is not convex, we can consider packing its convex hull, right?
yes, that is correct.
Critical test cases: The smallest bounding box is more difficult to find by search methods, so if you don't have an analytical solution for that, you should random-generate some test cases and try different number of search iterations to see if your result will change.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
Is there an analytic solution for the largest bounding box? I had to binary search to find the largest bounding box.

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:
Hi!
I am trying to solve this problem by rotating the given polygon from 0 to 2*pi radian and look if in this state package will have maximum or minimum area. I think that logic is OK and there's some error with precision (as usual). I can't find it, maybe people you can?? I dunno what to do

Code: Select all

``````program Project2;
{\$R-}{\$S-}{\$Q-}
procedure f(var x,y,beta: extended);
var
xt,yt: extended;
begin
xt := x*cos(beta) - y*sin(beta);
yt := x*sin(beta) + y*cos(beta);
x := xt;
y := yt
end;

var
i,n,ci: integer;
a,b: array [1..2,1..100] of extended;
alpha,min,max: extended;
minx,miny,maxx,maxy,s: extended;

begin

ci := 0;

while n<>0 do
begin
ci := ci + 1;
for i:=1 to n do

alpha := 0;
min := 20000000;
max := -min;

while alpha<=2*pi do
begin
b := a;
minx := 2000000;
miny := minx;
maxx := -minx;
maxy := -minx;

for i:=1 to n do
begin
f(b[1,i],b[2,i],alpha);
if b[1,i]<minx then
minx := b[1,i];
if b[2,i]<miny then
miny := b[2,i];
if b[1,i]>maxx then
maxx := b[1,i];
if b[2,i]>maxy then
maxy := b[2,i];
end;
s := abs(minx-maxx)*abs(miny-maxy);
if s > max then
max := s;
if s < min then
min := s;

alpha := alpha + pi/2000;

end;

writeln ('Minimum area = ',min:0:3);
writeln ('Maximum area = ',max:0:3);
writeln;

end;

end.
``````
[/code]
Now I lay me down to sleep...
my profile

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Can someone tell me the I/O below is right?

Code: Select all

``````25
6 47
88 102
147 963
-68 896
147 85
-32 0
14 687
452 398
-120 1325
400 -1
789 -102
987 652
1020 -157
698 -47
-321 -474
87 -12
0 0
144 -987
136 -488
989 121
102 1369
631 -789
-741 248
573 100
101 -983
0
``````
my output

Code: Select all

``````Gift 1
Minimum area = 3499579.388
Maximum area = 4196137.175
``````

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
My accepted code returns same output.
Ami ekhono shopno dekhi...
HomePage

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Code: Select all

``````10
6 20
7 15
8 30
10 78
-98 12
0 478
96 147
-36 -7436
1 -23
4 6
``````

Code: Select all

``````Gift 1
Minimum area = 1516378.765
Maximum area = 31316346.000
``````
or can you give me some I/O? thanks

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm