最近の2時

に答える

無知に解けますか?

すべての点間の距離を求めて比較することで,解くことができる.しかし,時間的複雑度はO(n 2)O(n^2)O(n 2)であり,絶対時間では解決できない.

分割征服アルゴリズム

分割征服アルゴリズムを使用して問題を解決するには、3つのコンポーネントを作成する必要があります.
最初のコンポーネントを作成するには、何に基づいて問題を区別する必要があります.中心点のx座標で分割する方法を簡単に思い出すことができます.ただし、このように分割すると、2つの点間のベースライン距離は比較されません.そのため、3つの問題を解決する必要があります.

ベースラインの左側から2点までの距離の最大値

ベースラインの右側から2点までの距離の最大値

2点間距離

ベースラインの最大値

連結プロセスは、3つの分割問題の答えの最小値を返します.しかし、問題があります.3つ目の問題を解決する方法を考えなければなりません.全左点と全右点をベースラインに対して比較した場合,時間的複雑度はO(n 2)O(n^2)O(n 2)であるため求められない.ここで洞察をしなければならない.ベースライン間の2点、すなわち1番目の質問の答えと2番目の質問の答えの最大値minDistanceDistanceDistanceDistanceDistance間の距離を比較する必要はありません.もっと遠く離れていると、最初の問題と2番目の問題よりも答えが大きいからです.私たちはもっと大きな価格を考える必要はありません.最高価格を求める必要があるからです.
ここまで考えると、x座標が同じでy座標だけが異なる点が多い場合、効率が低いことがわかります.この問題を解決するには、y座標で中間の点をソートし、一番下の点から別の一番上の点までの距離を順番に比較します.y座標との差が「最小距離」より大きい点を順番に比較する場合は、その点は比較を停止し、他の点を比較する必要があります.一部の点では、1つの点の最大最小距離から1つの点までの距離を求める必要があるため、時間的複雑度はO(n)O(n)O(n)O(n)O(n)である.
3番目のコンポーネントを特定する必要があります.分割領域内の点の個数が数以下である場合、分割すべきでないか否かを決定しなければならない.2個未満で分割を放棄して2点間の距離を返すと、3個残っている場合に1個と2個に分割される場合があります.分割領域の点数が1の場合、距離を求めることができないため、3点が残っている場合は、3点間のすべての距離を比較して最大値を返す必要があります.

じかんふくごうどぶんせき

1回の呼び出しは関数を半分に分割し、時間的複雑度O(n)O(n)O(n)O(n)の関数を呼び出して上記3番目の問題を解決するので、T(n)=2 T(n 2)+nT(n)=2 T({n\over 2})+nT(n)=2 T(n)+n)となる.主定理によれば,我々が実施したアルゴリズムの時間的複雑さはO(nloglogn)O(nlogn)O(nlogn)である.

インプリメンテーション

import java.util.*;

class Point {
    public int x;
    public int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getDistance(Point point) {
        return (this.x - point.x) * (this.x - point.x) + (this.y - point.y) * (this.y - point.y);
    }
}

public class Main {

    // 모든 점의 개수
    public static int n;
    // 모든 점
    public static Point[] points;
    // 답
    public static int result;

    public static void input() {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        points = new Point[n];

        for (int i = 0; i < n; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            points[i] = new Point(x, y);
        }

        Arrays.sort(points, new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                return o1.x - o2.x;
            }
        });
    }

    public static void solve() {
        result = getMinDistance(0, n - 1);
    }

    // 두 점들 간의 거리의 최솟값을 반환합니다.
    public static int getMinDistance(int left, int right) {
        // 기저 사례: 점들의 개수가 3개 이하면 브루트 포스로 계산
        if (right - left + 1 <= 3) {
            return getMinDistanceByBruteForce(left, right);
        }
        // 가운데 점의 x좌표 기준으로 문제 분할
        int mid = (right + left) / 2;
        int distance = Math.min(getMinDistance(left, mid), getMinDistance(mid + 1, right));
        // 가운데 영역 안의 문제 해결
        int middleLeft = left;
        int middleRight = right;
        int temp = points[mid].x - points[middleLeft].x;
        while (temp * temp > distance) {
            middleLeft++;
            temp = points[mid].x - points[middleLeft].x;
        }
        temp = points[middleRight].x - points[mid].x;
        while (temp * temp > distance) {
            middleRight--;
            temp = points[middleRight].x - points[mid].x;
        }
        distance = Math.min(distance, getMinDistanceInMiddle(distance, middleLeft, middleRight));
        return distance;
    }
    // 가운데 영역 안의 두 점들 간의 거리의 최솟값 계산
    public static int getMinDistanceInMiddle(int minDistance, int left, int right) {
        int distance = minDistance;
        // 기저 사례: 점들의 개수가 3개 이하면 브루트 포스로 계산
        int size = right - left + 1;
        if (size <= 3) {
            return getMinDistanceByBruteForce(left, right);
        }
        // 가운데 영역 안의 점들은 y좌표 기준으로 정렬함
        Point[] midPoints = new Point[size];
        for (int i = 0; i < size; i++) {
            midPoints[i] = points[left + i];
        }
        Arrays.sort(midPoints, new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                return o1.y - o2.y;
            }
        });
        // 2중 반복문이라서 시간 복잡도가 O(n^2)이라고 생각할 수 있지만 조건문 때문에 안쪽의 반복문은 최대 minDistance번 실행됨
        for (int i = 0; i < size; i++) {
            for (int j = i + 1; j < size; j++) {
                int temp = midPoints[j].y - midPoints[i].y;
                if (temp * temp >= distance) {
                    break;
                }
                distance = Math.min(distance, midPoints[i].getDistance(midPoints[j]));
            }
        }
        return distance;
    }
    // 브루트 포스로 영역 안의 두 점들 간의 거리의 최솟값 계산
    public static int getMinDistanceByBruteForce(int left, int right) {
        int distance = Integer.MAX_VALUE;
        for (int i = left; i <= right - 1; i++) {
            for (int j = i + 1; j <= right; j++) {
                distance = Math.min(distance, points[i].getDistance(points[j]));
            }
        }
        return distance;
    }

    public static void output() {
        System.out.println(result);
    }

    public static void main(String[] args) {
        input();
        solve();
        output();
    }
}

振り返る

実装前はアルゴリズムに問題はなかったと思いますが、タイムアウトが続いていたので、コードを逐一分析し、原因を特定するために様々な仮定を確立しました.
1.Scannerを使ってデータを受信する時間が長すぎますか?
スキャンプログラムを入力すると、BufferedReaderを入力するとタイムアウトが表示されます.問題解決後、BufferedReaderを使用するとScannerを使用する場合との時間差は約1.3倍になりますが、これはScannerの問題ではありません.
2.街をぶらつくときMath.pow()関数はもっと時間がかかりますか?
浮動小数点の乗算は整数の乗算よりも長いが、これは問題ではない.
3.変数を保存していませんが、もう一度計算するのに時間がかかりますか?

        for (int i = 0; i < size; i++) {
            for (int j = i + 1; j < size; j++) {
                if ((midPoints[j].y - midPoints[i].y) * (midPoints[j].y - midPoints[i].y) >= distance) {
                    break;
                }
                distance = Math.min(distance, midPoints[i].getDistance(midPoints[j]));
            }
        }

中間領域の点の距離を比較するための繰り返し文では、変数に格納するのではなく、比較するたびに2つの点のy座標の違いを計算しますか?と思ったけど.

        for (int i = 0; i < size; i++) {
            for (int j = i + 1; j < size; j++) {
                int temp = (midPoints[j].y - midPoints[i].y);
                if (temp * temp >= distance) {
                    break;
                }
                distance = Math.min(distance, midPoints[i].getDistance(midPoints[j]));
            }
        }

こうなっても結果は変わらない
4.並び順が遅いですか?それをリストに並べて並べ替えますか?
念のためCollectionssort()関数の実装コードを表示し、配列リストを配列に設定し、Arraysを設定します.配列をsort()にソートし、配列リストに再リストして返します.したがって、Collections.sort()関数はArraysです.sort()より速くはあり得ない.
本当の原因はgetMinDistance()関数でint middleLeft=0である.なぜなら.中間領域を定義する場合、関数を呼び出す際には入力パラメータの左側から考慮し、0から考慮する必要があるため、関数を呼び出すたびにパラメータに関係なく時間複雑度O(n)O(n)O(n)O(n)O(n)の操作が実行される.
コードを作るときはこのような小さなミスがたくさんあります.もっと集中する必要があります.