819 - Gifts Large and Small

All about problems in Volume 8. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

819 - Gifts Large and Small

Post by .. » 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?
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » 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.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » 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.

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Post by andysoft » 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 :oops:

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]
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

Post by Wei-Ming Chen » 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

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Aug 12, 2007 10:19 pm

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

Post by Wei-Ming Chen » Mon Aug 13, 2007 5:03 am

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » 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.
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 8 (800-899)”