[백준] 1064번 - 평행사변형 [Java]

https://www.acmicpc.net/problem/1064

 

[백준] 1064번 - 평행사변형 [Java]

[백준] 1064번 - 평행사변형 [Java]

---

1.  아이디어

 

삼각형을 만들 수 있는지 여부는 CCW 알고리즘을 활용해서 구했고, 평행사변형 둘레의 길이의 차의 최댓값은 기존 삼각형의 각 변의 길이를 크기 순으로 a, b, c라고 했을 때, 가장 짧은 둘레의 길이는 2 * (a + b), 가장 긴 둘레의 길이는 2 * (b + c)라는 점을 이용했다.

---

2. 문제풀이

 

세 점이 한 직선 위에 있으면 삼각형을 만들 수 없으므로 CCW의 값이 0인지 판단하는 방식으로 구현했다.

둘레의 길이의 차는 위 수학적 테크닉으로 간단하게 구할 수 있다.

---

3. 코드

 

import java.io.*;
import java.util.*;

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 x1 = Integer.parseInt(st.nextToken());
        int y1 = Integer.parseInt(st.nextToken());
        int x2 = Integer.parseInt(st.nextToken());
        int y2 = Integer.parseInt(st.nextToken());
        int x3 = Integer.parseInt(st.nextToken());
        int y3 = Integer.parseInt(st.nextToken());

        if (ccw(x1, y1, x2, y2, x3, y3) == 0) {
            System.out.println(-1);
        } else {
            double[] dist = {distance(x1, y1, x2, y2), distance(x2, y2, x3, y3), distance(x3, y3, x1, y1)};
            Arrays.sort(dist);

            System.out.println((dist[2] - dist[0]) * 2);
        }
    }

    // CCW 알고리즘
    private static int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
        return (x1 * y2 - x2 * y1) + (x2 * y3 - x3 * y2) + (x3 * y1 - x1 * y3);
    }

    private static double distance(int x1, int y1, int x2, int y2) {
        int dx = x1 - x2;
        int dy = y1 - y2;
        return Math.sqrt(dx * dx + dy * dy);
    }

}

---

4. 후기