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

문제 링크

---

1. 문제 풀이

서로 다른 세 점이 주어졌을 때, 적절한 점 $D$ 로 평행사변형을 만들 수 없으면 $-1$ 을 출력하고, 만들 수 있으면 만들 수 있는 평행사변형 중 가장 큰 둘레의 길이와 가장 작은 둘레의 길이의 차를 출력해야 하는 문제다.

평행사변형을 만들 수 없는 경우는 세 점이 일직선 상에 위치하는 경우로 세 점의 좌표가 $(x_A, y_A)$, $(x_B, y_B)$, $(x_C, y_C)$ 일 경우 $\dfrac{y_B-y_A}{x_B-x_A} = \dfrac{y_C-y_A}{x_C-x_A}$ 로 기울기를 비교하면 일직선 상에 위치하는지 알 수 있다. 이때 $x$ 좌표가 서로 일치할 수도 있고(분모가 $0$) 나눗셈의 경우 나머지가 버림처리 될 수 있으며 실수 타입은 부동소수점 오차가 생길 수 있기 때문에 $(y_B-y_A)\cdot(x_C-x_A) = (y_C-y_A)\cdot(x_B-x_A)$ 로 계산했다. 또는 CCW 알고리즘을 활용해 세 점이 일직선 상에 위치하는지 판단해도 된다.

세 점이 일직선 상에 위치하지 않을 경우 세 점으로 만들 수 있는 삼각형의 각 변마다 해당 변을 대각선으로 갖는 평행사변형을 만들 수 있는데 이 평행사변형의 둘레의 길이는 다른 두 변의 길이의 합의 두 배임을 이용하면 된다.

아래 그림과 같이 둘레의 길이가 $2 \cdot (a + b)$, $2 \cdot (b + c)$, $2 \cdot (c + a)$ 인 $3$ 개의 평행사변형을 만들 수 있다.(직각, 둔각 삼각형도 동일하다.)

이때 가장 큰 둘레의 길이와 가장 작은 둘레의 길이의 차는 $2 \cdot (가장\ 긴\ 변 - 가장\ 짧은\ 변)$ 이 됨을 이용하면 된다.

---

2. 코드

1. 기울기 판정 [Java]

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 xa = Integer.parseInt(st.nextToken());
        int ya = Integer.parseInt(st.nextToken());
        int xb = Integer.parseInt(st.nextToken());
        int yb = Integer.parseInt(st.nextToken());
        int xc = Integer.parseInt(st.nextToken());
        int yc = Integer.parseInt(st.nextToken());

        if ((yb - ya) * (xc - xa) == (yc - ya) * (xb - xa)) {
            System.out.println(-1);
        } else {
            double[] sides = {dist(xa, ya, xb, yb), dist(xb, yb, xc, yc), dist(xc, yc, xa, ya)};
            Arrays.sort(sides);

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

    static double dist(int x1, int y1, int x2, int y2) {
        return Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2));
    }
}

2. CCW [Java]

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 xa = Integer.parseInt(st.nextToken());
        int ya = Integer.parseInt(st.nextToken());
        int xb = Integer.parseInt(st.nextToken());
        int yb = Integer.parseInt(st.nextToken());
        int xc = Integer.parseInt(st.nextToken());
        int yc = Integer.parseInt(st.nextToken());

        if (ccw(xa, ya, xb, yb, xc, yc) == 0) {
            System.out.println(-1);
        } else {
            double[] sides = {dist(xa, ya, xb, yb), dist(xb, yb, xc, yc), dist(xc, yc, xa, ya)};
            Arrays.sort(sides);

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

    static int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
        return Integer.signum((x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1));
    }

    static double dist(int x1, int y1, int x2, int y2) {
        return Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2));
    }
}

3. 기울기 판정 [C++]

cout 은 소수점 아래 6자리까지만 출력하는 것이 기본값이기 때문에 fixed 와 setprecision(9) 을 통해 9자리까지 출력하도록 해줬다.

#include <bits/stdc++.h>
using namespace std;

double dist(int x1, int y1, int x2, int y2) {
    return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int xa, ya, xb, yb, xc, yc;
    cin >> xa >> ya >> xb >> yb >> xc >> yc;

    if ((yb - ya) * (xc - xa) == (yc - ya) * (xb - xa)) {
        cout << -1;
    } else {
        vector<double> v = {dist(xa, ya, xb, yb), dist(xb, yb, xc, yc), dist(xc, yc, xa, ya)};
        sort(v.begin(), v.end());

        cout << fixed << setprecision(9) << 2 * (v[2] - v[0]);
    }
}

4. CCW [C++]

cout 은 소수점 아래 6자리까지만 출력하는 것이 기본값이기 때문에 fixed 와 setprecision(9) 을 통해 9자리까지 출력하도록 해줬다.

#include <bits/stdc++.h>
using namespace std;

int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
    int cross = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
    return (cross > 0) - (cross < 0);
}

double dist(int x1, int y1, int x2, int y2) {
    return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int xa, ya, xb, yb, xc, yc;
    cin >> xa >> ya >> xb >> yb >> xc >> yc;

    if (ccw(xa, ya, xb, yb, xc, yc) == 0) {
        cout << -1;
    } else {
        vector<double> v = {dist(xa, ya, xb, yb), dist(xb, yb, xc, yc), dist(xc, yc, xa, ya)};
        sort(v.begin(), v.end());

        cout << fixed << setprecision(9) << 2 * (v[2] - v[0]);
    }
}

---

3. 풀이 정보

1. 기울기 판정 [Java]

언어	시간	메모리	코드 길이
Java 11	104 ms	14328 KB	1035 B

2. CCW [Java]

언어	시간	메모리	코드 길이
Java 11	100 ms	14540 KB	1175 B

3. 기울기 판정 [C++]

언어	시간	메모리	코드 길이
C++ 17	0 ms	2036 KB	587 B

4. CCW [C++]

언어	시간	메모리	코드 길이
C++ 17	0 ms	2036 KB	735 B

---