11315 - Attacker

fpavetic · Post by **fpavetic** » Sun Oct 21, 2007 12:18 pm

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

shanto86 · Post by **shanto86** » Sun Oct 21, 2007 3:09 pm

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?

Lomir · Post by **Lomir** » Mon Oct 22, 2007 10:50 am

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

shanto86 · Post by **shanto86** » Mon Oct 22, 2007 10:52 am

i think checking intersecting fact is going to take way more than N^2 in worst case!

shanto86 · Post by **shanto86** » Tue Oct 23, 2007 6:21 am

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!

fpavetic · Post by **fpavetic** » Tue Oct 23, 2007 2:29 pm

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

baodog · Post by **baodog** » Wed Oct 24, 2007 12:05 pm

See solution notes for "Soldiers" (identical problem) from the PKU POJ:

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

shanto86 · Post by **shanto86** » Wed Oct 24, 2007 12:11 pm

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!

shanto86 · Post by **shanto86** » Wed Oct 24, 2007 2:47 pm

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.

sclo · Post by **sclo** » Thu Oct 25, 2007 8:50 pm

i guess nlog n union of rectangle is considered to be easy in China.

sonyckson · Post by **sonyckson** » Mon Dec 24, 2007 3:56 am

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.