## 11315 - Attacker

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

fpavetic
Learning poster
Posts: 51
Joined: Sat Mar 04, 2006 8:00 pm

### 11315 - Attacker

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
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 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?
Self judging is the best judging!

Lomir
New poster
Posts: 19
Joined: Mon Sep 17, 2007 10:05 pm
Contact:
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
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
i think checking intersecting fact is going to take way more than N^2 in worst case!
Self judging is the best judging!

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
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!
Self judging is the best judging!

fpavetic
Learning poster
Posts: 51
Joined: Sat Mar 04, 2006 8:00 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
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am
See solution notes for "Soldiers" (identical problem) from the PKU POJ:

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

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 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!
Self judging is the best judging!

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 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.
Self judging is the best judging!

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
i guess nlog n union of rectangle is considered to be easy in China.

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina
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.