3125042_wa.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.*;

public class Main {

    private static final double EPS = 1e-8;

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        n++;

        int[] x = new int[n];
        int[] y = new int[n];

        for (int i = 1; i < n; i++) {
            x[i] = scanner.nextInt();
            y[i] = scanner.nextInt();
        }

        double[][] d = new double[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                d[i][j] = 1e100;
            }
        }

        for (int i = 1; i < n; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            d[a][b] = Math.hypot(x[a] - x[b], y[a] - y[b]);
            d[b][a] = d[a][b];
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    d[j][k] = Math.min(d[j][k], d[j][i] + d[i][k]);
                }
            }
        }

        int mini = 0;
        int minj = 0;
        double max = 0;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                boolean good = true;
                for (int k = 0; k < n; k++) if (k != i && k != j) {
                    if ((x[k] - x[i]) * (y[j] - y[i]) == (x[j] - x[i]) * (y[k] - y[i]) &&
                            x[k] >= Math.min(x[i], x[j]) && x[k] <= Math.max(x[i], x[j]) &&
                            y[k] >= Math.min(y[i], y[j]) && y[k] <= Math.max(y[i], y[j])) {
                        good = false;
                        break;
                    }
                }
                if (good) {
                    double dd = d[i][j] - Math.hypot(x[i] - x[j], y[i] - y[j]);
                    if (dd > max) {
                        max = dd;
                        mini = i;
                        minj = j;
                    }
                }
            }
        }

        if (max < EPS)
            System.out.println("-1");
        else
            System.out.println(mini + ' ' + minj);

    }


}