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

Post by andresw1 » Mon Mar 20, 2006 9:22 pm

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

Post by shahriar_manzoor » Mon Mar 20, 2006 10:12 pm

AFAIK, this problem is not solvable using pick's theorem.

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

Post by andresw1 » Mon Mar 20, 2006 10:57 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

Post by wook » Wed Mar 22, 2006 9:40 am

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.. :)

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Wed Mar 22, 2006 11:32 am

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

Post by kalinov » Wed Mar 22, 2006 2:24 pm

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

Post by kalinov » Wed Mar 22, 2006 2:36 pm

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?

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Wed Mar 22, 2006 2:50 pm

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:

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

Post by wook » Wed Mar 22, 2006 4:23 pm

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.^^
Sorry For My Poor English.. :)

User avatar
Hadi
Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:

Post by Hadi » Fri Mar 24, 2006 8:03 am

I am getting WA :( . Please give me some input/output ...

User avatar
Hadi
Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:

Post by Hadi » Fri Mar 24, 2006 8:15 am

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?

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Sat Mar 25, 2006 6:57 pm

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.

Post by aminallam » Tue Mar 28, 2006 2:35 pm

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

Post by domino » Tue Mar 28, 2006 5:30 pm

I have also used plane sweep , but i get WA. Does the polygon self-intersect? Could someone provide some testcases please?

User avatar
Hadi
Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:

Post by Hadi » Tue Mar 28, 2006 10:53 pm

The polygon does not have self-intersect. I've tested that.

Post Reply

Return to “Volume 110 (11000-11099)”