PROBLEM LINKSDIFFICULTYMEDIUM PREREQUISITESAd Hoc, Sweep Line PROBLEMYou are given a chess board with several bishops, and several obstacles. Considering that the movement of the Bishops is blocked by these obstacles, you wish to find the number of cells that are under threat from one or more Bishops. Note that if a cell is under threat from multiple Bishops, we must count it only once. QUICK EXPLANATIONWe can imagine each Bishop to be at the center of an X shaped region. The region is terminated by either the boundary of the chessboard or some obstacle. We can find the number of cells within this X shaped region. Now, for all the Bishops together, we can find the sum of of number of cells within their regions of attack. The regions of attack of different bishops may intersect (we can easily handle overlaps, as we will see below). These intersection points have been double counted! Finding the number of intersection points by use of a sweep line algorithm, we can count and then eliminate them. The implementation of this approach, can use several simplifications as described below. EXPLANATIONConsider bishops and obstacles in white cells and black cells separately We know that bishops in black cells do not share regions of attack with bishops in white cells. Thus, we can consider them as two separate cases for simplicity. The real benefit of introducing this differentiation is in the following simplification. Tilt the board by 45 degrees Now, each region of attack is a simple plus shaped region, built from a horizontal segment, and a vertical segment. We consider white and black on different boards, hence do not have to worry about how to not consider the intersection of segments from bishops which are rooted on cells of two separate colors. Consider a board of size 5 by 5. The alternate boards that should be considered are shown below Original Board. 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25 Assuming that the top left cell is colored black, let us look at the arrangement of all the black cells tilted by 45 degrees. We preserve the labels of the cells as showed above to make the mapping obvious.   1     11  7  3   21  17  13  9  5   23  19  15     25   Let us look at the arrangement of all the white cells tilted by 45 degrees.  6  2   16  12  8  4  22  18  14  10   24  20  Note how the black board is built from cells numbered odd, and the white board from cells numbered even. Consider horizontal segments and vertical segments Now, in each one of the subboards separately (black and white), we can consider the line segments that are attacked by bishops. We know that the segments will be vertical and horizontal. We can count the number of cells in each one of the segments. Next, we must find the number of intersection points caused by these segments. Reducing this from the sum of number of cells in all the segments leads us to the answer. Finding the number of intersections We have N horizontal and N vertical line segments (potentially fewer, because overlapping line segments from different bishops can be merged and considered as single line segment). We wish to find the number of points at which these line segments intersect. We already know that two line segments that overlap (touch each other sideways) can always be merged and considered as a single segment. Thus, each intersection can only happen between one horizontal segment, and one vertical segment. Let T, be an augmented binary tree that is aware of the dynamic order index of its members. This can be done in several ways, for example
Both the techniques above support each operation (add, delete and checkindex) in O(log N) time, where we may add at most N items. In the case of Fenwick's Tree, because the number of values that are added is much smaller than the range of values, we must relabel the values to a smaller range [1 ... number of values]. Let E represent the set of events for a Sweep Line algorithm. We will consider the following events
We can iterate through the list of events sorted by the xcoordinate. We handle the events as follows
Thus, we will know the number of intersection points. The overall complexity of the algorithm would be O(N log N), where N is the number of bishops. SETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 25 Mar '13, 00:19

include<stdio.h>include<conio.h>main() { int N,K,M; int i,counter,l,j; counter=0; printf("enter n,k,mn"); scanf("%d %d %d",&N,&K,&M); int arr[4][2]={{1,1},{1,1},{1,1},{1,1}}; int X,Y,U,V; int u,v,t; int bis[K][2]; int res[M][2]; printf("enter pos of bishopn"); for(i=0;i<K;i++) { scanf("%d %d",&X,&Y); bis[i][0]=X; bis[i][1]=Y; } printf("enter pos of othern"); for(i=0;i<M;i++) { scanf("%d %d",&U,&V); res[i][0]=U; res[i][1]=V; } for(i=0;i<K;i++) { for(j=0;j<4;j++) { t=1; u=0; v=0; while(u!=N && v!=N && u!=1 && v!=1) { u=bis[i][0]+(arr[j][0]t); v=bis[i][1]+(arr[j][1]t); for(l=0;l<M;l++) { if(u==res[l][0] && v==res[l][1]) { u=N; } } t++; counter++; } } } printf("%d",counter); getch(); return 0; } answered 20 Apr '13, 13:46
