intersection.java

计算水平线与垂直线交点个数问题。扫描方法计算。

package intersection;
import java.io.PrintWriter;
import java.util.Scanner;


class horizonal {
	int x1, x2, y;
	horizonal() {
		this.x1 = this.x2 = this.y;
	}
	horizonal(int x1, int x2, int y) {
		this.x1 = x1;
		this.x2 = x2;
		this.y = y;
	}
}
class vertical {
	int y1, y2, x;
	vertical() {
		this.x = this.y1 = this.y2;
	}
	vertical(int y1, int y2, int x) {
		this.y1 = y1;
		this.y2 = y2;
		this.x = x;
	}
}
public class intersection {
	
	private int search(vertical a[], int x, int length) {
		int begin = 0;
		int end = length - 1;
		for (int i = end / 2; begin != end; i = (begin + end + 1) / 2) {
			if (a[i].x == x)
				return i;
			else if (a[i].x < x) {
				end = i - 1;
			} else
				begin = i;
		}
		return begin;
	}
	private void swap(vertical a, vertical b) {
		vertical temp = new vertical(a.y1, a.y2, a.x);
		a.x = b.x;
		a.y1 = b.y1;
		a.y2 = b.y2;
		b.x = temp.x;
		b.y1 = temp.y1;
		b.y2 = temp.y2;
	}
	private void sort(vertical[] ver, int length) {
		int l = length - 1;
		for (int i = l / 2; i >= 0; i--)
			pushdown(ver, i, l);
		for (int i = l; i >= 1; i--) {
			swap(ver[0], ver[i]);
			pushdown(ver, 0, i - 1);
		}
	}
	void pushdown(vertical ver[], int first, int last) {
		int position;
		while (first <= last / 2) {
			if ((2 * first + 2) > last)
				position = last;
			else if (ver[first * 2 + 1].x > ver[first * 2 + 2].x)
				position = 2 * first + 2;
			else
				position = 2 * first + 1;
			if (ver[first].x > ver[position].x) {
				swap(ver[first], ver[position]);
				first = position;
			} else
				break;
		}
	}
	public static void main(String argv[]) throws java.io.IOException {
		
		java.io.FileInputStream fin = new java.io.FileInputStream("intersection.in");
		
		PrintWriter out = new PrintWriter("intersection.out");
		int v = 0, h = 0;
		
		Scanner in = new java.util.Scanner(fin);
		if (in.hasNextInt()) {
			h = in.nextInt();
			v = in.nextInt();
		}
		
		horizonal hor[] = new horizonal[h];
		vertical ver[] = new vertical[v];
		for (int i = 0; i < h && in.hasNextInt(); i++)
			hor[i] = new horizonal(in.nextInt(), in.nextInt(), in.nextInt());
		for (int i = 0; i < v && in.hasNextInt(); i++)
			ver[i] = new vertical(in.nextInt(), in.nextInt(), in.nextInt());
/*		for (int i = 0; i < h; i++)
			System.out.println("horizonal: " + hor[i].x1 + "," + hor[i].x2
					+ "," + hor[i].y);
		for (int i = 0; i < v; i++)
			System.out.println("vertical: " + ver[i].y1 + "," + ver[i].y2 + ","
					+ ver[i].x);*/
		intersection temp = new intersection();
		temp.sort(ver, v);
/*		for (int i = 0; i < v; i++) {
			System.out.println(ver[i].x);
		}*/
		java.util.ArrayList<int[]> list = new java.util.ArrayList<int[]>();
		for (int i = 0; i < h; i++) {
			int x = temp.search(ver, hor[i].x1, v);
			for (int j = x; j >= 0 && ver[j].x <= hor[i].x2; j--) {
				if (hor[i].y >= ver[j].y1 && hor[i].y <= ver[j].y2)
					list.add(new int[]{ver[j].x , hor[i].y});
			}
		}
		out.println(list.size());
		
		for (int i = 0; i < list.size(); i++)
			for (int j = 0; j < list.size() - i - 1; j++)
				if (list.get(j)[1] > list.get(j+1)[1]) {
					int[]temp1 =list.get(j);
					list.set(j, list.get(j+1));
					list.set(j+1,temp1);
				}
		for (int i = 0; i < list.size(); i++)
			for (int j = 0; j < list.size() - i - 1; j++)
				if (list.get(j)[0] > list.get(j+1)[0]) {
					int[]temp1 =list.get(j);
					list.set(j, list.get(j+1));
					list.set(j+1,temp1);
				}
		for (int i = 0; i < list.size(); i++)
			out.println(list.get(i)[0]+" "+list.get(i)[1]);
		fin.close();
		out.close();
	}

}