problem statement
In this problem you have to count the number of none-square rectangles in a given rectangle.
What I do is this, that I try to count all of
1*2, 1*3 ... 1*w
2*3, 2*4.... 2*w
......................
rectangles.
and I do this once for my rectangle and another time with the new rectangle with width and height swapped.
this is my code:
long long func(int w, int h)
{
long long res = 0;
for(int i = 1; i <= h; i ++)
for(int j = i+1; j <= w; j ++)
res += (w-j+1) * (h-i+1);
return res;
}
long long countRectangles(int w, int h)
{
return func( w, h ) + func( h, w );
}
How did I find this solution? I just tried to check it out on a piece of paper and I saw that there is a template for placing the rectangles with different width and heights in a larger rectangle.
For example if you want to place a 1*2 rectangle in a large rectangle, first you have to count how many of them are placed in a single row, (width-2+1) and multiply this number in height that is the number of 1*2 rectangles that are placed horizontally in a rectangle.
There are another solutions that I'm thinking about them, using 4 and 3 loops that I think they are trivial, and using 1 loop or even no loop that I'm thinking to understand them completely, then I'm gonna add them here.
I describe my solution or give some hints about the solution for algorithmic problems used in ICPC or online sites for programming contests.
Wednesday, January 12, 2011
Subscribe to:
Post Comments (Atom)
USACO - Prime Palindromes
I just skimmed the problem statement and panicked of the high boundary of the input, but something inside told me don't worry everyth...
-
Link to the problem on Timus Online Judge First of all there are two kinds of input which the answer is zero, first if sum % 2 == 1 or se...
-
Link to the problem on Timus Online Judge The problem statement is completely straight forward with no hidden tricks :). Yeah yeah I know...
-
Link to the problem on Timus Online Judge This is a Computational Geometry problem. No 3 points lie on the same line and this is a great...
No comments:
Post a Comment