10652 - Board Wrapping

All about problems in Volume 106. 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
abc
New poster
Posts: 15
Joined: Sun Dec 15, 2002 2:51 pm

10652 - Board Wrapping

Post by abc » Tue May 25, 2004 9:25 pm

Input/output please? WA!

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Wed May 26, 2004 9:03 pm

I also need some inputs for this problem.. I did the trivial Convex Hull.. is there any trick cases?

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

Post by rotoZOOM » Thu May 27, 2004 3:53 am

Larry wrote:I also need some inputs for this problem.. I did the trivial Convex Hull.. is there any trick cases?
I do the following:
1. place center of each rectangle at (0,0),
2. rotate all its points around Z-axis in CLOCKWISE order,
3. then transmit all points in compliance with real center of rectangle.
4. find convex hull
5. calculate its area
That's all
Did you do the same ?

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Thu May 27, 2004 4:24 am

That's basically what I did.. any I/O's? Maybe I'm doing something stupid precision-wise..

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

Post by rotoZOOM » Thu May 27, 2004 4:44 am

Larry wrote:That's basically what I did.. any I/O's? Maybe I'm doing something stupid precision-wise..
This how I output:
printf ("%.1lf %%\n",s*100.0/a);
s - is area of all rectangles,
a - is area of convex hull.
I am sorry I haven't any I/O, because my program
get AC from first attempt.
But I can check any input test on my AC program.

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Sat May 29, 2004 3:29 pm

I managed to come up with a solution that gives the correct answers to my test data, but WA from the judge.

I believe the problem lies in my code to find the four corners of each rectangle. Right now, the formula I use is:

angle_phi is the given angle in radians

angle_a = atan2( width, height )
angle_b = PI - angle_a - angle_phi
length = half the length of the diagonal of the rectangle = sqrt( w*w + h*h ) / 2

So point 1 =
[ x + (length * sin(angle_b)) , y + (length * cos(angle_b)) ]

and point 2 =
[ x - (length * sin(angle_b)) , y - (length * cos(angle_b)) ]



angle_c = PI - angle_phi
angle_d = PI - angle_a - angle_c

So point 3 =
[ x + (length * sin(angle_d)) , y - (length * cos(angle_d)) ]

and point 4 =
[ x - (length * sin(angle_d)) , y + (length * cos(angle_d)) ]




After I have all n * 4 points, I get the bottom most , left most and use simple convex hull algorithm to get the convex hull of all points.


Area of convex hull = area of polygon given by points on the hull

Area of boards = sum of all width * height




Finally, if area of convex hull == 0 or area of convexhull == area of rectangles (I use floating point comparison, eps = 1e-8), then print 100 %

else

printf("%.1llf %%\n", rectangle_area * 100.0 / hull_area);


(I use long double)




Can anyone tell me if I've done anything wrong?

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Wed Jun 09, 2004 10:06 am

Code: Select all

   for ( i = 0; i < n; i++ ) {
      scanf("%lf %lf %lf %lf %lf\n", &x, &y, &w, &l, &phi );
      phi = phi * PI / 180.0;
      cp = cos( phi ), sp = sin( phi );
      for ( j = 0; j < 4; j++ ) {
        k = i * 4 + j, nx = w * dx[j], ny = l * dy[j];
        area[k].x = ( nx * cp ) + ( ny * sp ) + x, area[k].y = ( ny * cp ) - ( nx * sp ) + y;
      }
}
This is basically my method.. what's wrong?

Here's some I/O from my program:

Code: Select all

2
5 5 5 5 20
100 100 5 5 20
3
436 85 5 12 1
566 66 12 15 5
1000 1000 1 1 75

Code: Select all

5.4 %
0.3 %
Is this correct? Thanks.

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

Post by rotoZOOM » Wed Jun 09, 2004 10:16 am

Larry wrote: This is basically my method.. what's wrong?

Here's some I/O from my program:

Is this correct? Thanks.
Yes, this is correct.
But your input data not correspond to problem description so well.
First number is number of tests.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Wed Jun 09, 2004 10:51 am

Ya, I took that into account, but just didn't post it so people can just concat it to their test cases..

My convex hull works for all the other problems, so I have no idea what is wrong.. and I don't think precision is a problem..

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

Post by rotoZOOM » Wed Jun 09, 2004 11:48 am

Larry wrote:

Code: Select all

   for ( i = 0; i < n; i++ ) {
      scanf("%lf %lf %lf %lf %lf\n", &x, &y, &w, &l, &phi );
      phi = phi * PI / 180.0;
      cp = cos( phi ), sp = sin( phi );
      for ( j = 0; j < 4; j++ ) {
        k = i * 4 + j, nx = w * dx[j], ny = l * dy[j];
        area[k].x = ( nx * cp ) + ( ny * sp ) + x, area[k].y = ( ny * cp ) - ( nx * sp ) + y;
      }
}
This is basically my method.. what's wrong?
This is part of my code (for vertex rotation)

Code: Select all

fscanf (in,"%d",&n);
s=0;
for (i=0;i<n;i++){
    fscanf (in,"%lf %lf %lf %lf %lf",&x,&y,&w,&h,&a);
    s=s+w*h;
    a=a*M_PI/180.0;
    pnt[i*4][0]=-w/2.0*cos(a)+h/2.0*sin(a)+x;
    pnt[i*4][1]=w/2.0*sin(a)+h/2.0*cos(a)+y;

    pnt[i*4+1][0]=w/2.0*cos(a)+h/2.0*sin(a)+x;
    pnt[i*4+1][1]=-w/2.0*sin(a)+h/2.0*cos(a)+y;

    pnt[i*4+2][0]=w/2.0*cos(a)-h/2.0*sin(a)+x;
    pnt[i*4+2][1]=-w/2.0*sin(a)-h/2.0*cos(a)+y;

    pnt[i*4+3][0]=-w/2.0*cos(a)-h/2.0*sin(a)+x;
    pnt[i*4+3][1]=w/2.0*sin(a)-h/2.0*cos(a)+y;
}		}
Then I calculate convex hull.
May be your code rotate vertex counter-clockwise instead of clockwise,
or some precisions error occurs ?

theemathas
New poster
Posts: 19
Joined: Mon Jan 07, 2013 9:30 am

10652: RE??

Post by theemathas » Tue Sep 24, 2013 7:55 pm

I'm keeping getting run-time error for no reason
I kept getting runtime error even after putting a try-catch block around the whole main function!

Could anyone please point out what caused the error?

Code: Select all

deleted
Note: those two comments in the code is the try-catch block I tried putting in, but still got runtime error. :o
Last edited by theemathas on Sun Oct 13, 2013 7:50 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10652 - Board Wrapping

Post by brianfry713 » Fri Oct 11, 2013 2:37 am

Try changing line 76 to:
while(hull.size() >= 2 && !ccw(hull[hull.size()-2],hull.back(),*it))
Check input and AC output for thousands of problems on uDebug!

theemathas
New poster
Posts: 19
Joined: Mon Jan 07, 2013 9:30 am

Re: 10652 - Board Wrapping

Post by theemathas » Sun Oct 13, 2013 7:52 am

Thanks, that was the reason I got RE. Now getting WA. (That reminds me of another problem I found before: WA->TL) I think I should be able to do it now.
brianfry713 wrote:Try changing line 76 to:
while(hull.size() >= 2 && !ccw(hull[hull.size()-2],hull.back(),*it))

Post Reply

Return to “Volume 106 (10600-10699)”