/* Author: Yiu Yu Ho This is a binary search problem. The following describes a O(n (log(n) + log(m))) solution: For x=K streets (vertical streets) (1) sort streets by x-value, increasing (2) sort points: first by y value (any fixed order), then by x-value (increasing) (3) for each distinct y-value of the points, obtain the sorted (by x) set of points with the same y value. (4) for each point, use binary search to find the street to the left (lower bound) and right (upper bound) of the point. (5) check to see if the point is viewable from those streets by checking whether it is blocked by the point to its left/right. Perform similar checks for y=K streets (horizontal streets) Count the number of points that are marked viewable */ import java.util.*; import java.io.*; public class park { public BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); public PrintStream out = System.out; public int n,m; public Tree[] v; public int[] xv,yv; public void main() { try { String L=in.readLine(); StringTokenizer tok=new StringTokenizer(L); n=new Integer(tok.nextToken()); m=new Integer(tok.nextToken()); while(n>0) { int i,j,k; v=new Tree[n]; for(i=0;i(); ArrayList YA=new ArrayList(); for(i=0;i0) { Arrays.sort(xv); Arrays.sort(v,new CYX()); i=0; while(ixv[0]) { a=lower(xv,v[k].x); if(k==i || v[k-1].xxv[b]) v[k].seen=true; } } i=j+1; } }//end if xv.length>0 if(yv.length>0) { Arrays.sort(yv); Arrays.sort(v,new CXY()); i=0; while(iyv[0]) { a=lower(yv,v[k].y); if(k==i || v[k-1].yyv[b]) v[k].seen=true; } } i=j+1; } }//end if yv.length>0 int R=0; for(i=0;i0 } catch(IOException ioe) { ioe.printStackTrace(); } } public int lower(int[] v,int key) { int low,hi,x; low = 0; hi=v.length-1; while(lowkey) return 0; return lower(v,key)+1; } public int[] IAL2ia(ArrayList A) { int[] r=new int[A.size()]; for(int i=0;i { public int compare(Tree A,Tree B) { if(A.y!=B.y) return A.y { public int compare(Tree A,Tree B) { if(A.x!=B.x) return A.x