백준
[백준] 2585 경비행기 [자바]
거북이같은곰
2022. 1. 19. 22:48
https://hae-ong.tistory.com/39
백준 2585번 경비행기
경비행기 시간 제한메모리 제한제출정답맞은 사람정답 비율 1 초 128 MB 2025 683 436 31.322% 문제 경비행기 독수리호가 출발지 S에서 목적지 T로 가능한 빠른 속도로 안전하게 이동하고자 한다. 이때,
hae-ong.tistory.com
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.StringTokenizer;
class Node {
int y;
int x;
Node(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main {
static int n, k;
static ArrayList<Node> list = new ArrayList<>();
static boolean[] xy;
public static void main(String arg[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
list.add(new Node(0,0));
for(int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine(), " ");
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
list.add(new Node(a, b));
}
int left = 0;
int right = 1500;
int result = 0;
while(left <= right) {
xy = new boolean[1001];
int mid = (left + right) / 2;
double a = mid * mid * 100;
if(bfs(a)) {
left = mid+1;
}
else {
right = mid-1;
result = mid;
}
}
System.out.println(result);
}
static boolean bfs(double dis) {
LinkedList<Integer> q = new LinkedList<>();
q.add(0);
int cnt = 0;
int size = 0;
double dis1;
double disto;
while(!q.isEmpty()) {
size = q.size();
if(cnt > k)
return true;
for(int i = 0; i < size; i++) {
int num = q.poll();
if(!xy[num]) {
xy[num] = true;
for(int j = 1; j <= n; j++) {
int tx = list.get(j).x-list.get(num).x;
int ty = list.get(j).y-list.get(num).y;
dis1 = Math.pow(tx, 2) + Math.pow(ty, 2);
if(dis1 <= dis) {
int rx = 10000-list.get(j).x;
int ry = 10000-list.get(j).y;
disto = Math.pow(rx, 2) + Math.pow(ry, 2);
if(disto <= dis) {
return false;
}
q.add(j);
}
}
}
}
cnt++;
}
return true;
}
}