## 11315 - Attacker

**Moderator:** Board moderators

### 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

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

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?

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!

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

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

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!

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!