BOJ_17093 : Total Circle

👉 문제링크

17093번: Total Circle

---

---

🔸 문제 분석 🔸

• 한 점을 중점으로 여러 좌표를 지나는 원은 타원모양까지 생각하면 무수히 많다.
  • 문제 조건에서 최소크기의 원의 최대 반지름이라 했으므로, 중점과 가장 먼 좌표까지의 거리다.
• 모든 중점에서 구한 반지름의 최대값들 중에서 가장 큰 값을 출력한다.
• 최대값 찾기가 2번있는 셈이고, for문이 중첩되어 한 번씩 비교하는 형태이다.
  • n, m의 최대값은 1000이므로 O(n^2)에서 최대 계산량은 1,000,000 (백만)으로 1초 미만이다.
    따라서 제한시간 1초를 넘지 않는다.
• x, y의 크기가 10^7 == 10,000,000(천만) 까지 이고, 반지름 계산에서 제곱하게 된다.
  • 제곱하면 100,000,000,000,000(백경) 이므로 int를 초과한다...long을 사용해야한다.

🔸 코드 🔸

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        ArrayList<Pair> nl = new ArrayList<>();
        ArrayList<Pair> ml = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            nl.add(new Pair(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            ml.add(new Pair(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        long answer = 0;
        for (int i = 0; i < m; i++){
            long rr = 0;
            for (int j = 0; j < n; j++){
                long temp = (long)(Math.pow(nl.get(j).x - ml.get(i).x, 2) + Math.pow(nl.get(j).y - ml.get(i).y, 2));
                if (temp > rr) {
                    rr = temp;
                }
            }
            if (rr > answer){
                answer = rr;
            }
        }
        System.out.println(answer);
    }
}

class Pair {
    int x,y;
    Pair(int x, int y){
        this.x = x;
        this.y = y;
    }
}

🔸 코드 해석 🔸

• 좌표 계산을 해야하므로, Pair라는 클래스를 만들어서 x, y를 함께 저장했다.
  • ArrayLIst<> 의 인자로 넣으며, 사용할 자료형을 Pair로 지정한다.
• 중점과 좌표들의 거리를 계산한다.
  • [반지름^2 == (x-x`)^2 + (y-y`)^2 ] 공식을 사용한다. (제곱 사용 -> long형 필요)
  • 나온 반지름의 제곱값중 최대값을 rr에 저장한다.
• 나오는 rr중 최대값을 answer에 저장하고 최종 출력한다.

---

🔸 end 🔸

• 그려지는 원이 정확한 원인 줄 알고 잘못 접근해서 많이 틀렸었다.
• 타원형으로 그려진다고 생각이 가니, 왜 최소넓이의 최대 반지름인지 알 수 있었다.
• 풀이가 적은 문제여서 더 내 오류를 알아치리기 어려웠지만, 풀고나니 간단했고 브론즈 1문제였지만 많은 공부가 된 것 같다.