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?

[Adrian Kuegel]

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]

Is there an analytic solution for the largest bounding box? I had to binary search to find the largest bounding box.

[andysoft]

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

  readln (n);

  ci := 0;

  while n<>0 do
  begin
    ci := ci + 1;
    for i:=1 to n do
      readln (a[1,i],a[2,i]);

    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 ('Gift ',ci);
    writeln ('Minimum area = ',min:0:3);
    writeln ('Maximum area = ',max:0:3);
    writeln;

    readln (n)
  end;

end.

[/code]

[Wei-Ming Chen]

I have got wrong answer

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

Please help, thanks

[Jan]

My accepted code returns same output.

[Wei-Ming Chen]

and how about this I/O ?

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]

Same output as mine. You can post your code, then I can make random cases and run both the codes.