10652  Board Wrapping
Moderator: Board moderators
10652  Board Wrapping
Input/output please? WA!

 Learning poster
 Posts: 63
 Joined: Mon Dec 22, 2003 5:05 am
 Location: Russia, Chelyabinsk
 Contact:
I do the following:Larry wrote:I also need some inputs for this problem.. I did the trivial Convex Hull.. is there any trick cases?
1. place center of each rectangle at (0,0),
2. rotate all its points around Zaxis 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 ?

 Learning poster
 Posts: 63
 Joined: Mon Dec 22, 2003 5:05 am
 Location: Russia, Chelyabinsk
 Contact:
This how I output:Larry wrote:That's basically what I did.. any I/O's? Maybe I'm doing something stupid precisionwise..
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.
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 = 1e8), 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?
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 = 1e8), 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?

 Guru
 Posts: 647
 Joined: Wed Jun 26, 2002 10:12 pm
 Location: Hong Kong and New York City
 Contact:
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;
}
}
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 %

 Learning poster
 Posts: 63
 Joined: Mon Dec 22, 2003 5:05 am
 Location: Russia, Chelyabinsk
 Contact:
This is part of my code (for vertex rotation)Larry wrote:This is basically my method.. what's wrong?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; } }
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;
} }
May be your code rotate vertex counterclockwise instead of clockwise,
or some precisions error occurs ?

 New poster
 Posts: 19
 Joined: Mon Jan 07, 2013 9:30 am
10652: RE??
I'm keeping getting runtime error for no reason
I kept getting runtime error even after putting a trycatch block around the whole main function!
Could anyone please point out what caused the error?
Note: those two comments in the code is the trycatch block I tried putting in, but still got runtime error.
I kept getting runtime error even after putting a trycatch block around the whole main function!
Could anyone please point out what caused the error?
Code: Select all
deleted
Last edited by theemathas on Sun Oct 13, 2013 7:50 am, edited 1 time in total.

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 10652  Board Wrapping
Try changing line 76 to:
while(hull.size() >= 2 && !ccw(hull[hull.size()2],hull.back(),*it))
while(hull.size() >= 2 && !ccw(hull[hull.size()2],hull.back(),*it))
Check input and AC output for thousands of problems on uDebug!

 New poster
 Posts: 19
 Joined: Mon Jan 07, 2013 9:30 am
Re: 10652  Board Wrapping
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))