2005 East Central Regional : Square Count

wktang · Post by **wktang** » Sun Oct 01, 2006 9:26 am

Did anyone solve the problem from 2005 East Central America regional contest problem F: Square Count?

http://acmicpc-live-archive.uva.es/nuev ... php?p=3377

I found that the problem statement contradicting:

No two rooms will overlap, though they may share a side.

And the judge's input contain overlapping rooms!!! I've solved the problem by not counting the shared blocks between overlapping rooms. I'm pretty sure that the judge's input should not contain any overlapping rooms, but I might be wrong... If you've solved this problem, I would love to hear what did you think when solving this problem.

Darko · Post by **Darko** » Sun Oct 01, 2006 10:10 am

I am not sure - I never assumed that rooms might overlap. When I read the rooms in, I added squares per each room to the count (and afterwards I looked for the ones that spanned two rooms). If some of them overlapped I would've had too many.

(By "overlap" I assume you mean - "a corner of one room is in the interior of another")

wktang · Post by **wktang** » Sun Oct 01, 2006 5:24 pm

I obtained the sample input from the regional site:
http://acm.ashland.edu/2005/problem-set.html

I've got all test cases correct except for test cases 23-32 (which my output shows more room).

Here's what I found in the 23rd test case: (room in (x1, y1), (x2, y2) format)

Room 1 : (5542, 5201), (5583, 5152)
Room 446: (5484, 5274), (5555, 5175)

These 2 rooms are overlapping each other...

Darko, are you able to test the sample input from the site? I wonder if your output matches the sample output for test cases 23-32? ( since you said you never assumed that rooms might overlap. )

Darko · Post by **Darko** » Sun Oct 01, 2006 6:45 pm

Interesting... they do overlap. And I do get the correct (or "correct") answer. But if rectangles overlap, my solution shouldn't give the right answer.

I probably had the same approach as the original solution. In representing my rectangles I take mins and maxes, then to find "common area", I compare min-max pairs, if they are equal, they share a side, then I count those squares (if shared side > 2)...

I'll just send you the code in a PM.