백준 1393 자바(Java) 음하철도 구구팔 - 수선의 발, 반직선

태그

• 기하학
• 수선의 발
• 반직선

특징

수선의 발을 구하면 풀리는 간단한 문제가 아닌, 수선의 발이 철도의 경로내에 존재하는지 까지 고려해야하는, 즉 수선의 발, 선분위의 점 의 2개의 개념이 필요한 문제이다.

아래의 Mermaid 다이어그램으로 요약이 가능하다.

아래는 위의 Mermaid 다이어그램 코드이다.

graph TD
  수선의발 --> 경로{철도경로
  내에존재}
  경로 -->|YES|B[수선의발이
							  최단거리지점]
  경로 -->|NO|A[출발점이
							  최단거리지점]

코드

나의 경우는 반직선, 수선의 발에 대한 개념을 객체화로 해결하려고 했으나, 사실 이 문제를 풀기위해서는 이렇게까지 복잡한 구현이 필요없긴하다…

*** 문제에서 사용된 메서드만 표현해서 아래와 같은 구현이 불필요해 보일 수 있지만, 기하학에 주로 사용되는 로직들을 미리 구현해서 문제풀이에 활용하고 있으며 꽤 편리하다

static void solve() throws Exception {
	int targetX = scan.nextInt();
	int targetY = scan.nextInt();
	int sx = scan.nextInt();
	int sy = scan.nextInt();
	int dx = scan.nextInt();
	int dy = scan.nextInt();
	Point2D targetPoint = new Point2D(targetX, targetY);
	Point2D startPoint = new Point2D(sx, sy);
	Vector2D vector = new Vector2D(dx, dy);
	Line2D line = new Line2D(startPoint, vector);
	// 수선의 발
	Point2D foot = line.getFoot(targetPoint);
	Ray2D ray = new Ray2D(startPoint, vector);
	
	// 다이어그램 내 로직
	if (ray.isOn(foot)) {
		sb.append(Math.round(foot.x)).append(' ').append(Math.round(foot.y)).append('\\n');
	} else {
		sb.append(startPoint.x).append(' ').append(startPoint.y).append('\\n');
	}
}

// 2차원에서의 점 - 직선,반직선 정의에 사용
static class Point2D {
	double x;
	double y;

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

// 2차원 방향벡터 - 직선,반직선 정의에 사용
static class Vector2D {
	double x;
	double y;

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

	public double dot(Vector2D other) {
		return x * other.x + y * other.y;
	}

	public double getLengthSquare() {
		return x * x + y * y;
	}
}

// 2차원 직선 - 수선의 발 계산에 사용
static class Line2D {
	Point2D p;
	Vector2D v;

	public Line2D(Point2D p1, Vector2D v) {
		this.p = p1;
		this.v = v;
	}
	public Point2D getFoot(Point2D p1) {
		Vector2D pToP1 = new Vector2D(p, p1);
		double dot = pToP1.dot(v);
		double vLengthSquare = v.getLengthSquare();
		return p.add(v.multiply(dot / vLengthSquare));
	}
}

// 2차원 반직선 - 수선의 발이 반직선 위에 있는지 검사
static class Ray2D {
	Point2D p;
	Vector2D v;

	public Ray2D(Point2D p1, Vector2D v) {
		this.p = p1;
		this.v = v;
	}

	public boolean isOn(Point2D p1) {
		Vector2D vec2 = new Vector2D(p, p1);
		if (crossProduct(vec2, v) == 0) {
			return vec2.dot(v) > 0;
		}
		return false;
	}
}

// 두 벡터의 외적
public static double crossProduct(Vector2D v1, Vector2D v2) {
	return Math.abs(v1.x * v2.y - v1.y * v2.x);
}