문제 출처
https://www.acmicpc.net/problem/11662
11662번: 민호와 강호
민호와 강호가 2차원 좌표 평면 위에 있다. 민호는 점 A(Ax, Ay)에서 점 B(Bx, By)를 향해 걸어가고 있고, 강호는 점 C(Cx, Cy)에서 점 D(Dx, Dy)를 향해 걸어가고 있다. 민호와 강호는 동시에 출발하고, 민호가 점 B에 도착하는 순간 강호도 점 D에 도착한다. 또, 두 사람은 항상 일정한 속도로 걸어간다. 두 사람의 거리가 가장 가까울 때, 거리를 구하는 프로그램을 작성하시오. 두 점 (x1, y1), (x2, y2)사이의 거리
www.acmicpc.net
접근 방식 및 풀이
- 삼분탐색 이나 미분으로 해결할 수 있지만, 삼분탐색을 이용하여 해결하였다.
- 아래 블로그를 참고하여 삼분탐색을 통해 해결하였다.
https://mslim8803.tistory.com/13
백준(BOJ) 11662 : 민호와 강호 (JAVA)
문제링크 : https://www.acmicpc.net/problem/11662 11662번: 민호와 강호 민호와 강호가 2차원 좌표 평면 위에 있다. 민호는 점 A(Ax, Ay)에서 점 B(Bx, By)를 향해 걸어가고 있고, 강호는 점 C(Cx, Cy)에서 점 D..
mslim8803.tistory.com
소스 코드
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
double aX1 = sc.nextDouble();
double aY1 = sc.nextDouble();
double aX2 = sc.nextDouble();
double aY2 = sc.nextDouble();
double cX1 = sc.nextDouble();
double cY1 = sc.nextDouble();
double cX2 = sc.nextDouble();
double cY2 = sc.nextDouble();
// 오차가 10의 -6승까지
int interval = 1000000;
double aDX = (aX2-aX1)/interval;
double aDY = (aY2-aY1)/interval;
double cDX = (cX2-cX1)/interval;
double cDY = (cY2-cY1)/interval;
//시작점의 거리
double min = getDistance(aX1, aY1, cX1, cY1);
for (int i = 1; i <=interval ; i++) {
double tmp = getDistance(aX1 + aDX*i, aY1+ aDY*i, cX1+cDX*i, cY1+cDY*i);
if(tmp < min){
min = tmp;
}
}
System.out.println(min);
}
public static double getDistance(double x1, double y1, double x2, double y2){
return Math.sqrt(Math.pow(x2-x1, 2) + Math.pow(y2-y1, 2));
}
}
결과
'Competition > Baekjoon' 카테고리의 다른 글
| [백준] 10815번 자바 숫자카드 (0) | 2020.03.31 |
|---|---|
| [백준] 2805번 자바 나무자르기 (0) | 2020.03.29 |
| [백준] 1517번 자바 버블정렬 (0) | 2020.03.29 |