Page 1 of 1

11315 - Attacker

Posted: Sun Oct 21, 2007 12:18 pm
by fpavetic
can someone please give a hint or an idea for this problem?

my idea was to rotate the plane for 45 degrees but it didn't handle the boundary constraint ( it counted fields outside the chessboard as well )

Filip

Posted: Sun Oct 21, 2007 3:09 pm
by shanto86
Think about handling the white cells and black cells seperately.

But after that i dont know. AFAIK the NlogN solution (Klee's method) for Union of rectangle is too complex to code. And N^2 seems not to be feasible here! So i am not sure what to do from here!

If NlogN is the one that is to be used here, can any one please refer me to some site or send me his/her code?

Posted: Mon Oct 22, 2007 10:50 am
by Lomir
I think line sweeping will help us.
Two intersecting rectangles will can always divide into three non intersecting ones. And non intersecting rectangles can be sorted by thier y value.

So let's sort rectangles by their X cordinate. Now we will hold examined rectanges in RBTree by their Y cordinnate.
Then two rectangles intersect we change them into three non rectangles.
When we examine second point of rectangle it is removed from the tree, we add his area to an answer.

It is just a guess, I do not have AC :)

Posted: Mon Oct 22, 2007 10:52 am
by shanto86
i think checking intersecting fact is going to take way more than N^2 in worst case!

Posted: Tue Oct 23, 2007 6:21 am
by shanto86
well there is a problem with the union of rectangle procedure. note that some rectangle may get out of board. and in that case what to do? coz then only making union does not work!

Posted: Tue Oct 23, 2007 2:29 pm
by fpavetic
shanto86 wrote:well there is a problem with the union of rectangle procedure. note that some rectangle may get out of board. and in that case what to do? coz then only making union does not work!
that is my problem as well :)

Posted: Wed Oct 24, 2007 12:05 pm
by baodog
See solution notes for "Soldiers" (identical problem) from the PKU POJ:

http://acm.pku.edu.cn/JudgeOnline/showc ... st_id=1251

Posted: Wed Oct 24, 2007 12:11 pm
by shanto86
ya i saw that this morning, (some one gave the link at TC forum).

But how the judge says that the first part is easy to compute? To me the second part is easy to compute. And for the first part i cant think of other way than using NlgN union of rectangle! Now if the judge wants to say that NlgN computation is easy then i dont have anything to say!

Posted: Wed Oct 24, 2007 2:47 pm
by shanto86
YUPPY!!!

GOT AC :)

My timing is, .890s. I am not sure, but you people may try it with N^2 algorithm.

My algorithm is: Computing the first part in NlgN.
Then doing the second part in also NlgN time.

Posted: Thu Oct 25, 2007 8:50 pm
by sclo
i guess nlog n union of rectangle is considered to be easy in China.

Posted: Mon Dec 24, 2007 3:56 am
by sonyckson
Hello, i have seen there is a called Bentley's algorithm to get the union of n rectangles in O ( n log n ) ... but i havent found any tutorial or source to read about it.... could anyone give me some link? or some hints, if the idea is not so difficult?, thanks. Eric.