Poj Solution 2318

http://poj.org/problem?id=2318

/* @author:zeropinzuo */
import java.io.*;
import java.util.*;

public class Main{
 static Scanner cin;
 public static void main(String args[]){
  cin = new Scanner(System.in);
  while(run() != false)
    ;
  }
  
static boolean run(){
   int n = cin.nextInt();
   if(n==0)
    return false;
   Box box = new Box(n, cin);
   System.out.println();
   return true;
 }
}

class Box{
  int n,m;
  int X1,Y1,X2,Y2;

  PartitionList pList;

  public Box(int n, Scanner cin){
    this.n = n;
    m = cin.nextInt();
    X1 = cin.nextInt();
    Y1 = cin.nextInt();
    X2 = cin.nextInt();
    Y2 = cin.nextInt();

    int[] map = new int[n+1];
    Partition.setBound(Y1, Y2);
    pList = new PartitionList(n);

    for(int i=0;i< n;i++){
    pList.add(new Partition(cin.nextInt(), cin.nextInt()));
    map[i] = 0;
    }
    map[n] = 0;

    for(int i=0;i< m;i++)
    map[pList.search(cin.nextInt(), cin.nextInt())]++;
    for(int i=0;i<=n;i++)
    System.out.println(i+": "+map[i]);
  }


}

class Partition{
  static int Y1, Y2;
  int U,L;

  public Partition(int U, int L){
    this.U = U;
    this.L = L;
  }

  static void setBound(int y1, int y2){
    Y1 = y1;
    Y2 = y2;
  }

 int compareTo(int X, int Y){
   double position = L+(double)(Y-Y2)*(U-L)/(Y1-Y2);
   if(X > position)
     return -1;
   else
    return 1;
 }
}

class PartitionList{
  Partition[] list;

  private int count=0;

  public PartitionList(int n){
    list = new Partition[n];
  }

  void add(Partition p){
    list[count++] = p;
  }

  int search(int X, int Y){
    if(list[0].compareTo(X, Y) == 1)
    return 0;
    else if(list[list.length-1].compareTo(X, Y) == -1)
    return list.length;
    else
    return find(0, list.length-1, X, Y);
   }

 
 private int find(int start, int end, int X, int Y){
   if((start+1)==end)
    return end;

   int mid = (start+end)/2;

   if(list[mid].compareTo(X, Y) == 1)
    return find(start, mid, X, Y);
   else 
    return find(mid, end, X, Y);
 }
}