Poj Solution 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();
    return false;
   Box box = new Box(n, cin);
   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;
    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;
    return find(0, list.length-1, X, Y);

 private int find(int start, int end, int X, int Y){
    return end;

   int mid = (start+end)/2;

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

This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *