기하 - 두 선분 사이의 거리

라이님 블로그에서 공부했음을 밝힙니다

https://blog.naver.com/kks227/220794097589

 

https://www.acmicpc.net/problem/11563

11563번: 연돌이와 고잠녀

이 문제로 연습하면 좋다.

 

 

두 선분 사이의 거리를 구할 땐 크게 2가지 경우를 살펴보면 된다.

 

1.

이 경우 d = min({DA,DB}, {CA,CB});  그냥 두 정점간 거리 중 최단 거리를 뽑아주면 된다.

 

2.

이 경우 대충 보면 d = min({dist(C, AB), dist(D,AB)}, {dist(A,CD), dist(B,CD)}); 인데,

점과 선분 사이의 거리를 보기 위해선, 예를들어 왼쪽 그림을 봤을 떄, 점 C에서 선분 AB에 내린 수선의 발 R이 선분 AB위에 있어야 한다. (점 D에서 직선 AB에 내린 수선의 발은 선분 AB 밖에 있다)

 

위의 조건을 만족하기 위해선, iproduct(AB,AC) > 0 && iproduct(BA,BC) > 0 이어야 한다.

 

왼쪽 그림을 보며 이제 점과 수선의 발 사이의 거리(점과 선분 사잉의 거리)를 구하는 법을 알아보자.

신발끈 공식 등을 이용해서 삼각형 ABC의 면적*2을 구한 후, 선분AB로 나눠주면 된다. 

 

typedef pair<double, double> Point;
typedef Point Vec;
typedef pair<Point, Point> Road;

long double distBetweenRoad(Road r1, Road r2) {
	Point A = r1.first, B = r1.second, C = r2.first, D = r2.second; 

	long double mn = min(min(distBetweenPoint(A, C), distBetweenPoint(A, D)),
		min(distBetweenPoint(B, C), distBetweenPoint(B, D)));

	long double h = 1e9;
	if (innerProduct({ C.first - A.first, C.second - A.second }, { B.first - A.first, B.second - A.second })>0 &&
		innerProduct({ C.first - B.first, C.second - B.second }, { A.first - B.first, A.second - B.second })>0) {
		long double s = triangle(A, B, C);
		h = min(h, s / distBetweenPoint(A, B) );
	}
	if (innerProduct({ D.first - A.first, D.second - A.second }, { B.first - A.first, B.second - A.second })>0 &&
		innerProduct({ D.first - B.first, D.second - B.second }, { A.first - B.first, A.second - B.second }) >0) {
		long double s = triangle(A, B, D);
		h = min(h, s / distBetweenPoint(A, B) );
	}
	if (innerProduct({ A.first - C.first, A.second - C.second }, { D.first - C.first, D.second - C.second }) > 0 &&
		innerProduct({ A.first - D.first, A.second - D.second }, { C.first - D.first, C.second - D.second }) > 0) {
		long double s = triangle(A, C, D);
		h = min(h, s / distBetweenPoint(C, D));
	}
	if (innerProduct({ B.first - C.first, B.second - C.second }, { D.first - C.first, D.second - C.second }) > 0 &&
		innerProduct({ B.first - D.first, B.second - D.second }, { C.first - D.first, C.second - D.second }) > 0) {
		long double s = triangle(B, C, D);
		h = min(h, s / distBetweenPoint(C, D));
	}
	return min(mn, h);
}