## 11016 - Square Counting

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

andresw1
New poster
Posts: 27
Joined: Sat Mar 18, 2006 5:04 pm

### 11016 - Square Counting

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?

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.

andresw1
New poster
Posts: 27
Joined: Sat Mar 18, 2006 5:04 pm
After I spend a lot of time I found that it is useless here:) So what is the approach?

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of
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.
Sorry For My Poor English..

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
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.

kalinov
New poster
Posts: 27
Joined: Tue Mar 29, 2005 3:10 pm
Location: Croatia
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.

kalinov
New poster
Posts: 27
Joined: Tue Mar 29, 2005 3:10 pm
Location: Croatia
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?

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
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

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of
To kalinov :

Thanks for pointing out my wrong thoughts! I was just a fool.
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.^^
Sorry For My Poor English..

Hadi
Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:
I am getting WA . Please give me some input/output ...

Hadi
Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:
I got AC . 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?

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
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
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.

aminallam
New poster
Posts: 39
Joined: Thu Dec 08, 2005 12:51 pm
Location: Suez, Egypt.
I need a good article about plane-sweeping, that will help me solve this problem.

domino
New poster
Posts: 19
Joined: Thu Dec 25, 2003 6:01 pm
I have also used plane sweep , but i get WA. Does the polygon self-intersect? Could someone provide some testcases please?

Hadi
Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:
The polygon does not have self-intersect. I've tested that.