Hello,
There must be some kind of formula for this problem. All I know is Pig's theorem but here it doesn't help a lot. If there is no such formula I was thinking for plain sweep. Can you give some hints?
11016 - Square Counting
Moderator: Board moderators
-
shahriar_manzoor
- System administrator & Problemsetter
- Posts: 399
- Joined: Sat Jan 12, 2002 2:00 am
hmm
AFAIK, this problem is not solvable using pick's theorem.
How about think of Divide and Conquer?
Divide a large rectangle into four smaller rectangles.
Coordinates are lower than 10000,
therefore at the worst cases time complexity is about O(10000 * 10000 * lg(10000) ).
But this rarely happens.
In fact, N is quite small (N ≤ 100), so it will fit in the time limit.
Divide a large rectangle into four smaller rectangles.
Coordinates are lower than 10000,
therefore at the worst cases time complexity is about O(10000 * 10000 * lg(10000) ).
But this rarely happens.
In fact, N is quite small (N ≤ 100), so it will fit in the time limit.
Sorry For My Poor English.. 
"For each test case, output a line containing two space separated integers, the number of light and dark squares completely encompassed by the polygon in descending order."Cho wrote:Since the square in the first row and first column is dark (from the figure), I couldn't understand why the second sample output is "1 0".
Do I mis-understand something?
Btw, I think plane-sweep will do.
Funny, I've missed that part too. I did the plane-sweep also and got accepted.
I don't think you can get it within time limits with divide and conquer approach, but it depends on how complex polygons in the input are.wook wrote:How about think of Divide and Conquer?
Divide a large rectangle into four smaller rectangles.
Coordinates are lower than 10000,
therefore at the worst cases time complexity is about O(10000 * 10000 * lg(10000) ).
But this rarely happens.
In fact, N is quite small (N ≤ 100), so it will fit in the time limit.
For each rectangle you have to test is it completely inside or outside the polygon. As you said, there can be as much as 10000*10000*lg10000 rectangles in the worst case. So, I believe the total complexity is O( N*10000*10000*lg10000 ) then.
Have you tried to implement it?
THX A LOT... That's tricky!kalinov wrote:"For each test case, output a line containing two space separated integers, the number of light and dark squares completely encompassed by the polygon in descending order."
Funny, I've missed that part too. I did the plane-sweep also and got accepted.
And I'm just toooooo careless
. Please give me some input/output ...
. My mistake was foolish. I realized it so soon. (And I don't need any input/outputs anymore)Hi eveyone,
Just want to remind all onething, if you have got AC on this problem, try also 10031.
If your program isn't too slow, just change the input/output format is ok....
Because I just re-use my code of 10031 :p
Just want to remind all onething, if you have got AC on this problem, try also 10031.
If your program isn't too slow, just change the input/output format is ok....
Because I just re-use my code of 10031 :p
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.