POJ2318:POJ2318
题意:
有一个长方形，左上顶点坐标(x1,y1)，右下顶点坐标(x2,y2)，被N条上端点为(up,y1)，下端点为(low,y2)的线段分成N+1部分，向长方形中扔M个质点，每个点坐标(x,y)，求落在每一部分的点的数量。

Input:
每组数据第一行6个整数N,M,x1,y1,x2,y2，其后N行，每行2个整数up,low，再其后M行，每行2个整数x,y，输入到N=0结束。
Output：
每组输出共N+1行，每行格式为
#: @
#代表长方形的分块序号，从0开始到N结束，@代表该分块中的质点数，冒号后有一空格，两组输出之间有一个空行
说明：
1<=N<=5000;1<=M<=5000;所有线段互不相交;所有质点不会落在线段上;所有质点不会落在长方形外面，但落会落在边界上，也视为落在内部;所有线段按从左到右呈现在输入中。
解题思路：
遍历m条线段,用叉积来判断点在线段左面还是右面，如果在右面则判断下一条线段，在左面，就相应区域的点总数++，如果在最后一条线右面，则是最后一个区域的点总数++，5条线段可以分成6个区域。

几个注意点:(容易出现空指针异常)

  • java的类中成员不要初始化为null;
  • java的类中类需要借助前一个类来实例化。
  • 使用叉积函数时，注意实参与形参的对应。
import java.util.Arrays;
import java.util.Scanner;

//每组数据第一行6个整数N,M,x1,y1,x2,y2，
//其后N行，每行2个整数up,low，再其后M行，
//每行2个整数x,y，输入到N=0结束。
public class POJ2318 {
	static int n, m;
	static Line[] l = new Line[5001];// 线数组
	static int[] count = new int[5002];// 区域数组

	static class Dian {//点类
		int x = 0;
		int y = 0;
	}

	static class Line {//线类
		Dian a = new Dian();
		Dian b = new Dian();
	}

	static int chaji(Dian p0, Dian p1, Dian p2) {// 叉积函数
		return (p0.x - p2.x) * (p1.y - p2.y) - (p1.x - p2.x) * (p0.y - p2.y);
	}

	static void judge(Dian d) {// 判断位置
		for (int i = 0; i < n; i++) {
			if (chaji(d, l[i].a, l[i].b) > 0)
				continue;
			else {
				count[i]++;
				return;//返回上一层
			}
		}
		count[n]++;
		return;
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		for (int i = 0; i < l.length; i++)
			l[i] = new Line();
		Dian left_up = new Dian();// new三个点
		Dian right_low = new Dian();
		Dian temp = new Dian();
		while (in.hasNext()) {
			n = in.nextInt();
			if (n == 0)
				break;
			m = in.nextInt();
			left_up.x = in.nextInt();// in对角点
			left_up.y = in.nextInt();
			right_low.x = in.nextInt();
			right_low.y = in.nextInt();
			for (int i = 0; i < n; i++) {// in线段顶点
				l[i].a.x = in.nextInt();
				l[i].b.x = in.nextInt();
				l[i].a.y = left_up.y;
				l[i].b.y = right_low.y;
			}
			for (int i = 0; i < m; i++) {//in质点
				temp.x = in.nextInt();
				temp.y = in.nextInt();
				judge(temp);
			}
			for (int i = 0; i <= n; i++) {
				System.out.println(i + ": " + count[i]);
			}
			System.out.println("");
			Arrays.fill(count, 0);
		}
	}
}