import java.util.; import java.io.; class Main { static final double eps = 1e-10; static int n; static Point[] P = new Point[10000 + 5]; static class Point { double x, y; int id; public Point() {} public Point(double x, double y, int id) { this.x = x; this.y = y; this.id = id; } } static int dcmp(double x) { if (Math.abs(x) < eps) return 0; return x < 0 ? -1 : 1; } static class Vector { double x, y; public Vector(double x, double y) { this.x = x; this.y = y; } } static Vector minus(Point A, Point B) { return new Vector(A.x - B.x, A.y - B.y); } static double Cross(Vector A, Vector B) { return A.x * B.y - A.y * B.x; } static boolean cmp(Point A, Point B) { return dcmp(Cross(minus(A, P[0]), minus(B, P[0]))) < 0; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { n = sc.nextInt(); P[0] = new Point(sc.nextDouble(), sc.nextDouble(), 1); for (int i = 1; i < n; ++i) { P[i] = new Point(sc.nextDouble(), sc.nextDouble(), i + 1); if (P[i].x < P[0].x || (P[i].x == P[0].x && P[i].y < P[0].y)) swap(P, 0, i); } Arrays.sort(P, 1, n, Main::cmp); System.out.println(P[0].id + " " + P[n / 2].id); } } static void swap(Point[] P, int i, int j) { Point temp = P[i]; P[i] = P[j]; P[j] = temp; } }解释这段代码的运行过程

该程序的功能是给定平面上的 n 个点，找出其中距离第一个点最近和最远的两个点，并输出它们的编号。

具体的运行过程如下：

1. 读入点的个数 n 和 n 个点的坐标信息，将第一个点设为 P[0]。

2. 对剩余的 n-1 个点进行排序，排序的基准是以第一个点 P[0] 为原点建立的极角排序。排序后，P[1] 是极角最小的点，P[n-1] 是极角最大的点。

3. 输出距离第一个点最近和最远的两个点的编号，分别是 P[0] 和 P[n/2]。

在排序时，程序使用了极角排序算法，即以一个点为原点，按照与该点的连线与 x 轴正半轴的夹角从小到大排序。排序算法的时间复杂度是 O(nlogn)。在排序完成后，程序只需要找到 P[0] 和 P[n/2] 这两个点即可，时间复杂度为 O(1)。

同时，程序还进行了一些简单的数学计算和数组操作，这些操作的时间复杂度是 O(n) 级别的，可以忽略不计。因此，总的时间复杂度为 O(nlogn)。

相关问题

import java.util.Scanner; public class Test1 { 晋涛 public static void main(String[] args) { Sy

import java.util.Scanner;

public class Test1 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("请输入您的姓名：");
String name = scanner.nextLine();
.out.println("您好，" + name + "！");
}
}

这段代码是一个简单的Java程序，它使用了Java标准库中的Scanner类来实现用户输入和输出。首先，我们通过创建Scanner对象来获取用户的输入。然后，使用nextLine()方法读取用户输入的姓名，并将其存储在name变量中。最后，通过System.out.println()方法将问候语和用户的姓名输出到控制台。

import java.util.InputMismatchException;

import java.util.InputMismatchException 是 Java 中的一个 import 语句，用于导入 java.util 包中的 InputMismatchException 类。InputMismatchException 是一个继承自 java.util.NoSuchElementException 的异常类，通常在输入不匹配的情况下抛出。例如，在使用 Scanner 类从控制台读取输入时，如果输入的数据类型与所需的数据类型不匹配，则会抛出 InputMismatchException 异常。

导入 java.util.InputMismatchException 类后，就可以在代码中使用该类，例如：

import java.util.Scanner;
import java.util.InputMismatchException;

public class MyClass {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        try {
            int num = scanner.nextInt();
            System.out.println("输入的数字是：" + num);
        } catch (InputMismatchException e) {
            System.out.println("输入的不是数字！");
        }
    }
}

在上面代码中，我们使用 Scanner 类从控制台读取输入，如果输入的不是数字，则会抛出 InputMismatchException 异常，并被 catch 块捕获并处理。