풀이
삼분 탐색 문제이다.
삼분 탐색이란 이분 탐색과 비슷하지만 그래프값이 2차함수처럼 아래위로 볼록한 함수일 경우에 가능한 탐색이다.
그래프를 3등분하여 범위를 좁혀 가며 찾는 방법이다.
3분 탐색 자체는 알겠지만 문제에 적용을 어텋게 하는지 몰라서 결국 제대로 풀지 못했다.
-
C/C++
-
Python
-
Java
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // 2023-08-16 BOJ-11664(선분과 점) | |
| #include <iostream> | |
| #include <algorithm> | |
| #include <math.h> | |
| using namespace std; | |
| int main() { | |
| double ax, ay, az, bx, by, bz, cx, cy, cz; | |
| scanf("%lf %lf %lf %lf %lf %lf %lf %lf %lf", &ax, &ay, &az, &bx, &by, &bz, &cx, &cy, &cz); | |
| double mid1, mid2; | |
| for (int i = 0; i < 1000000; i++) { | |
| // 3등분 점을 구한다 | |
| double x1 = ax + (bx - ax)/3; | |
| double x2 = ax + 2 * (bx - ax)/3; | |
| double y1 = ay + (by - ay)/3; | |
| double y2 = ay + 2 * (by - ay)/3; | |
| double z1 = az + (bz - az)/3; | |
| double z2 = az + 2 * (bz - az)/3; | |
| mid1 = (x1 - cx) * (x1 - cx) + (y1 - cy) * (y1 - cy) + (z1 - cz) * (z1 - cz); | |
| mid2 = (x2 - cx) * (x2 - cx) + (y2 - cy) * (y2 - cy) + (z2 - cz) * (z2 - cz); | |
| if (mid1 < mid2) { | |
| bx = x2; | |
| by = y2; | |
| bz = z2; | |
| } | |
| else { | |
| ax = x1; | |
| ay = y1; | |
| az = z1; | |
| } | |
| } | |
| printf("%.9lf", min(sqrt(mid1), sqrt(mid2))); | |
| return 0; | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import math | |
| ax, ay, az, bx, by, bz, cx, cy, cz = map(float, input().split()) | |
| for _ in range(1000000): | |
| # 3등분 점을 구한다 | |
| x1 = ax + (bx - ax) / 3 | |
| x2 = ax + 2 * (bx - ax) / 3 | |
| y1 = ay + (by - ay) / 3 | |
| y2 = ay + 2 * (by - ay) / 3 | |
| z1 = az + (bz - az) / 3 | |
| z2 = az + 2 * (bz - az) / 3 | |
| mid1 = (x1 - cx) * (x1 - cx) + (y1 - cy) * (y1 - cy) + (z1 - cz) * (z1 - cz) | |
| mid2 = (x2 - cx) * (x2 - cx) + (y2 - cy) * (y2 - cy) + (z2 - cz) * (z2 - cz) | |
| if mid1 < mid2: | |
| bx = x2 | |
| by = y2 | |
| bz = z2 | |
| else: | |
| ax = x1 | |
| ay = y1 | |
| az = z1 | |
| result = min(math.sqrt(mid1), math.sqrt(mid2)) | |
| print("{:.9f}".format(result)) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.util.Scanner; | |
| public class Main { | |
| public static void main(String[] args) { | |
| Scanner scanner = new Scanner(System.in); | |
| double ax = scanner.nextDouble(); | |
| double ay = scanner.nextDouble(); | |
| double az = scanner.nextDouble(); | |
| double bx = scanner.nextDouble(); | |
| double by = scanner.nextDouble(); | |
| double bz = scanner.nextDouble(); | |
| double cx = scanner.nextDouble(); | |
| double cy = scanner.nextDouble(); | |
| double cz = scanner.nextDouble(); | |
| double mid1 = 0; | |
| double mid2 = 0; | |
| for (int i = 0; i < 1000000; i++) { | |
| double x1 = ax + (bx - ax) / 3; | |
| double x2 = ax + 2 * (bx - ax) / 3; | |
| double y1 = ay + (by - ay) / 3; | |
| double y2 = ay + 2 * (by - ay) / 3; | |
| double z1 = az + (bz - az) / 3; | |
| double z2 = az + 2 * (bz - az) / 3; | |
| mid1 = (x1 - cx) * (x1 - cx) + (y1 - cy) * (y1 - cy) + (z1 - cz) * (z1 - cz); | |
| mid2 = (x2 - cx) * (x2 - cx) + (y2 - cy) * (y2 - cy) + (z2 - cz) * (z2 - cz); | |
| if (mid1 < mid2) { | |
| bx = x2; | |
| by = y2; | |
| bz = z2; | |
| } else { | |
| ax = x1; | |
| ay = y1; | |
| az = z1; | |
| } | |
| } | |
| System.out.printf("%.9f", Math.min(Math.sqrt(mid1), Math.sqrt(mid2))); | |
| scanner.close(); | |
| } | |
| } |