자바 4225 쓰레기 슈트 (링크)
풀이
볼록 껍질(컨벡스 헐 알고리즘)을 이용해 푸는 문제이다.
간단히 말하면, 수많은 점들이 있을 때, 가장 외곽의 점들을 이어 모든 점을 둘러쌀 수 있다면 그 외곽 점들이 볼록 껍질이 되는 것이다. 자세한 설명은 아래 링크에서 참조하면 좋을 것이다.
컨벡스 헐 알고리즘
먼저, 입력받은 점들을 배열에 담으면서 y좌표가 가장 작은 점을 저장해 놓자. 이 점이 기준점이 될 것이다.
기준점을
root라고 하자.
x 좌표가 -1이고root와 y 좌표가 같은 임시 점을tmp라고 하고
배열을 전부 돌면서tmp,root와의 각도를 기준으로 내림차순 정렬하자.
( root 본인은 첫 번째여야 하기 때문에 가장 큰 값으로 하자 )
이제 스택을 만들고 정렬된 배열의 0번째, 1번째 인덱스 점을 차례대로 넣자.
이후 2번째 인덱스부터 배열을 돌면서 ccw가 1이면( 반시계 방향 ) 스택에 추가하고, 이전에 있던 점을 pop하고 그 전 단계부터 다시 진행한다.
이제 스택에 볼록 껍질에 해당하는 점들만 들어가 있을 것이다.
이 스택을 배열로 만들어 반복문을 돌며 i, i+1의 점들로 변을 만들어 다른 점들과의 거리를 계산하고 가장 큰 값을 저장하자.
이제 각 변마다 계산한, 가장 거리가 큰 값들 중에서 가장 작은 값을 찾으면 끝이다.
최종 코드 및 결과
import java.io.*;
import java.util.*;
public class Main {
static class Dot implements Comparable<Dot> { // 점 객체
double x, y, deg; // 좌표와 기준점과의 각도 저장
Dot(double a, double b) {
x = a;
y = b;
}
@Override
public int compareTo(Dot o) {
int comp = Double.compare(o.deg, this.deg);
// 기준점과의 각도기준 내림차순 정렬
if (comp != 0) return comp;
// 기준점과의 각도가 같다면 기준점으로부터의 거리기준 내림차순
return Double.compare(dist(root, o), dist(root, this));
}
}
static Dot root; // 기준이 될 점
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
int N, tc = 0;
while((N = Integer.parseInt(br.readLine())) != 0) { // N이 0이면 종료
tc++;
// 기준점은 y좌표가 가장 작아야 하기 때문에 최대값인 (0, 10000)으로 초기화
root = new Dot(0, 10000);
Dot[] dots = new Dot[N];
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
dots[i] = new Dot(x, y);
// y좌표가 가장 작은 점을 저장
if (dots[i].y <= root.y) root = dots[i];
}
// 기준점과의 각도를 각 점에 저장
for(int i = 0; i < N; i++) dots[i].deg = deg(dots[i]);
Arrays.sort(dots); // 기준점과의 각도기준 내림차순 정렬
Stack<Dot> s = new Stack<>();
s.push(dots[0]);
s.push(dots[1]); // 스택을 만든 뒤 0, 1번째 점 추가
for(int i = 2; i < N; i++) {
Dot second = s.pop(), first = s.peek(), next = dots[i];
if (ccw(first, second, next) < 0) i--; // 시계방향이면 이전단계로
else {s.push(second); s.push(next);} // 반시계면 second, next 추가
}
int size = s.size();
Dot[] border = new Dot[size]; // 스택을 배열로 변환
for(int i = 0; i < size; i++) border[i] = s.pop();
double res = 10000; // 가장 작은 값을 구해야 하기 때문에 최대값인 10000으로 초기화
for(int i = 0, len = border.length; i < len; i++) {
int line1 = i, line2 = (i+1)%len; // 한 변을 이룰 점 두 개의 인덱스
double max = 0; // 거리가 최대인 점을 구해야 하기 때문에 최소값인 0으로 초기화
for(int cur = 0; cur < len; cur++) {
if (cur != line1 && cur != line2) { // 변을 이루는 점은 건너뜀
// 점과 변 사이의 거리 최대값을 저장
max = Math.max(max, dist(border[cur], border[line1], border[line2]));
}
}
// 저장해 놓았던 최대값들 중 최소값 저장
res = Math.min(res, max);
}
sb.append("Case ").append(tc).append(": ");
sb.append(String.format("%.2f", Math.ceil(res*100)/100)).append("\n");
}
System.out.print(sb);
}
static double deg(Dot d) { // 점 root를 지나고 x축과 평행한 직선과의 각도 계산
if (root.x == d.x && root.y == d.y) return 7; // 기준점이라면 2*pi보다 큰 7로 초기화
// x좌표 -1, root와 y좌표가 같은 임시 점이 있다고 생각하고 root, d 와 각도 계산
double p12 = Math.pow(root.x+1, 2);
double p23 = Math.pow(root.x-d.x, 2) + Math.pow(root.y-d.y, 2);
double p31 = Math.pow(d.x+1, 2) + Math.pow(d.y-root.y, 2);
return Math.acos((p12+p23-p31) / (2*Math.sqrt(p12)*Math.sqrt(p23)));
}
static int ccw(Dot a, Dot b, Dot c) { // ccw 계산
double res = (a.x*b.y + b.x*c.y + c.x*a.y) - (a.x*c.y + c.x*b.y + b.x*a.y);
return res < 0 ? -1 : 1;
}
static double dist(Dot a, Dot l1, Dot l2) { // 점과 직선 사이 거리 계산
double X, Y, dx = l1.x-l2.x, dy = l1.y-l2.y;
if (dx == 0) {
X = l1.x;
Y = a.y;
} else if (dy == 0) {
X = a.x;
Y = l1.y;
} else {
X = (dx/dy*a.x + dy/dx*l1.x + a.y - l1.y)/(dx/dy + dy/dx);
Y = dy/dx*(X-l1.x) + l1.y;
}
return dist(a, new Dot(X, Y));
}
// 점과 점 사이 거리 계산
static double dist(Dot a, Dot b) {return Math.sqrt(Math.pow(a.x-b.x, 2) + Math.pow(a.y-b.y, 2));}
}
만재 개발자