OJ Board

Posted: **Tue Dec 28, 2004 8:16 am**

Can anyone provide some critical example?

If the input polygon is not convex, we can consider packing its convex hull, right?

Posted: **Fri Feb 04, 2005 8:42 pm**

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.

Posted: **Sat Apr 01, 2006 12:13 am**

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

Posted: **Mon Jul 16, 2007 4:06 pm**

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]

Posted: **Sun Aug 12, 2007 7:02 pm**

I have got wrong answer

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

Code: Select all

my output

Code: Select all

Gift 1
Minimum area = 3499579.388
Maximum area = 4196137.175

Please help, thanks

Posted: **Sun Aug 12, 2007 10:19 pm**

My accepted code returns same output.

Posted: **Mon Aug 13, 2007 5:03 am**

and how about this I/O ?

Code: Select all

Code: Select all

Gift 1
Minimum area = 1516378.765
Maximum area = 31316346.000

or can you give me some I/O? thanks

Posted: **Mon Aug 13, 2007 9:41 pm**

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

OJ Board

819 - Gifts Large and Small

819 - Gifts Large and Small