# 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++){
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];
}

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);
}
}

```
This entry was posted in poj. Bookmark the permalink.