Page 1 of 2

11016 - Square Counting

Posted: Mon Mar 20, 2006 9:22 pm
by andresw1
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?

hmm

Posted: Mon Mar 20, 2006 10:12 pm
by shahriar_manzoor
AFAIK, this problem is not solvable using pick's theorem.

Posted: Mon Mar 20, 2006 10:57 pm
by andresw1
After I spend a lot of time I found that it is useless here:) So what is the approach?

Posted: Wed Mar 22, 2006 9:40 am
by wook
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.

Posted: Wed Mar 22, 2006 11:32 am
by Cho
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.

Posted: Wed Mar 22, 2006 2:24 pm
by kalinov
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.
"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.

Posted: Wed Mar 22, 2006 2:36 pm
by kalinov
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.
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.

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?

Posted: Wed Mar 22, 2006 2:50 pm
by Cho
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.
THX A LOT... That's tricky!
And I'm just toooooo careless :oops:

Posted: Wed Mar 22, 2006 4:23 pm
by wook
To kalinov :

Thanks for pointing out my wrong thoughts! I was just a fool. :cry:
and I am sorry I posted hastily although I haven't implemented it,

Now I got how to make it using Plane-sweeping.
Thank you very much.^^

Posted: Fri Mar 24, 2006 8:03 am
by Hadi
I am getting WA :( . Please give me some input/output ...

Posted: Fri Mar 24, 2006 8:15 am
by Hadi
I got AC :D . My mistake was foolish. I realized it so soon. (And I don't need any input/outputs anymore)
Regards,
Hadi Moshayedi

PS : Mr. Kalinov, have u ever been to world finals till now?

Posted: Sat Mar 25, 2006 6:57 pm
by ..
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

Posted: Tue Mar 28, 2006 2:35 pm
by aminallam
I need a good article about plane-sweeping, that will help me solve this problem.

Posted: Tue Mar 28, 2006 5:30 pm
by domino
I have also used plane sweep , but i get WA. Does the polygon self-intersect? Could someone provide some testcases please?

Posted: Tue Mar 28, 2006 10:53 pm
by Hadi
The polygon does not have self-intersect. I've tested that.