読者です 読者をやめる 読者になる 読者になる

AOJ 2003: 線分の交差

競技プログラミング AOJ

解法

書くだけ。線分の交差とかはライブラリにしておくと便利っぽい。

コード

import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;

public class Main {

	public static void main(String[] args) {
		int N = nextInt();
		for (int k = 0; k < N; k++) {
			P A = new P(nextInt(), nextInt());
			P B = new P(nextInt(), nextInt());

			int n = nextInt();

			Geo2D geo2d = new Geo2D();

			ArrayList<CrossPoint> list = new ArrayList<CrossPoint>();
			for (int i = 0; i < n; i++) {
				P S = new P(nextInt(), nextInt());
				P T = new P(nextInt(), nextInt());

				int o = nextInt();// 1ならば自社
				int l = nextInt();// 0ならば地下

				if (o == 0) {
					// 他社なら反転
					l = (l + 1) % 2;
				}

				if (geo2d.cross(A, B, S, T)) {
					P crossP = geo2d.intersection_ls(A, B, S, T);
					list.add(new CrossPoint(crossP.x, crossP.y, l == 0));
				}
			}
			Collections.sort(list);

			boolean now = true;
			P nowP = new P(-100000, -100000);
			int ans = 0;
			for (int i = 0; i < list.size(); i++) {
				if (i != 0 && now != list.get(i).under) {
					double x = nowP.x - list.get(i).x;
					double y = nowP.y - list.get(i).y;
					double dist = Math.sqrt(x * x + y * y);
					if (dist > 1e-9) {
						ans++;
					}
				}
				now = list.get(i).under;
				nowP.x = list.get(i).x;
				nowP.y = list.get(i).y;
			}
			System.out.println(ans);

		}

	}

	static int nextInt() {
		int c;
		try {
			c = System.in.read();
			while (c != '-' && (c < '0' || c > '9'))
				c = System.in.read();
			if (c == '-')
				return -nextInt();
			int res = 0;
			while (c >= '0' && c <= '9') {
				res = res * 10 + c - '0';
				c = System.in.read();
			}
			return res;
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return -1;
	}
}

class CrossPoint implements Comparable<CrossPoint> {
	double x, y;
	boolean under;// 地下ならtrue
	double EPS = 1e-9;

	public CrossPoint(double x, double y, boolean under) {
		this.x = x;
		this.y = y;
		this.under = under;
	}

	public int compareTo(CrossPoint o) {
		// 基本x座標で昇順にソートしつつ、同じならy座標でソートする
		if (Math.abs(x - o.x) > EPS)
			return (int) Math.signum(x - o.x);
		else
			return (int) Math.signum(y - o.y);
	}
}

class P implements Comparable<P> {
	double x, y;
	double EPS = 1e-9;

	public P(double x, double y) {
		this.x = x;
		this.y = y;
	}

	public int compareTo(P o) {
		if (Math.abs(x - o.x) > EPS)
			return (int) Math.signum(x - o.x);
		else
			return (int) Math.signum(y - o.y);
	}
}

// 平面幾何系ライブラリもどき
class Geo2D {

	double EPS = 1e-9;

	/* 線分abと線分stは交差するか */
	boolean cross(P a, P b, P s, P t) {
		if (ex(a, b, s) * ex(a, b, t) > 0)
			return false;
		if (ex(b, a, s) * ex(b, a, t) > 0)
			return false;
		if (ex(t, s, a) * ex(t, s, b) > 0)
			return false;
		return ex(s, t, a) * ex(s, t, b) < EPS;
	}

	/* ベクトルstとsrの外積 */
	double ex(P s, P t, P r) {
		double x1 = t.x - s.x;
		double y1 = t.y - s.y;
		double x2 = r.x - s.x;
		double y2 = r.y - s.y;
		return x1 * y2 - x2 * y1;
	}

	// a1,a2を端点とする線分とb1,b2を端点とする線分の交点計算
	P intersection_ls(P a1, P a2, P b1, P b2) {
		double d1 = Math.abs(ex(b1, a1, b2));
		double d2 = Math.abs(ex(b1, a2, b2));
		double t = d1 / (d1 + d2);
		return new P(a1.x + (a2.x - a1.x) * t, a1.y + (a2.y - a1.y) * t);
	}

	/* 線分abと点Pの距離 */
	double dist(P a, P b, P p) {
		double x1 = b.x - a.x;
		double y1 = b.y - a.y;
		double x2 = p.x - a.x;
		double y2 = p.y - a.y;
		return Math.abs((x1 * y2 - x2 * y1)) / Math.hypot(x1, y1);
	}

	/* 点pは線分ab上にあるかどうか */
	boolean on(P a, P b, P p) {
		if (Math.abs(a.x - b.x) < EPS)
			return Math.min(a.y, b.y) <= p.y && p.y <= Math.max(a.y, b.y);
		double alpha = (b.y - a.y) / (b.x - a.x);
		double beta = a.y - alpha * a.x;
		if (Math.abs(p.y - (alpha * p.x + beta)) > EPS)
			return false;
		return Math.min(a.x, b.x) <= p.x && p.x <= Math.max(a.x, b.x);
	}
}