## 2005 East Central Regional : Square Count

Do you want to discuss about these problems? Go now!
Users are shared (no need to re-register).

Moderator: Board moderators

wktang
New poster
Posts: 8
Joined: Mon Jul 03, 2006 11:27 pm

### 2005 East Central Regional : Square Count

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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 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
New poster
Posts: 8
Joined: Mon Jul 03, 2006 11:27 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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am