java - 初级 Java 算法辅助

Question

我需要帮助编写一个程序，该程序以 (X,Y) 的形式给出指定数量的坐标点。将给出的点数是程序的第一行；它可以通过扫描仪读取。

我需要计算用直线 x = a 和 y = b 覆盖所有点的最小面积。因此，面积将是 a * b(矩形面积)。

但是必须去掉一个坐标点(X，Y)来优化面积。被删除的点应尽可能减少面积。我需要帮助编写算法才能这样做。

这是我得到的示例输入和输出::

样本输入

4

2 4

1 1

5 2

17 25

样本输出

12

---

在本例中，第一行输入(4)表示将输入四个点。接下来的四行是 (x, y) 形式的坐标。最后一个点 (17, 25) 作为异常值被移除，剩下前三个点。

如果剩下的三个点被绘制出来，它们都可以在一个盒子里(3 x 4)，因此输出是 12； (3 * 4)。这条线像本例一样在点上就可以了。然而，异常值并不总是最后一个点，或者非常大。异常值可能非常小，只需将面积最小化即可。

--这是我到目前为止所拥有的(我知道它不是很多..)-请帮助我!

这主要是我需要帮助的算法......

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

public class Area {

    public static void main(String args[]) {

        Scanner scan = new Scanner(System.in);

        int numOfPoints = scan.nextInt();
        int Xcoordinates[] = new int[numOfPoints];
        int Ycoordinates[] = new int[numOfPoints];


        for (int i = 0; i <= numOfCows - 1; i++) {
            Xcoordinates[i] = scan.nextInt();
            Ycoordinates[i] = scan.nextInt();
        }
    }
}

可能的伪代码(从上面继续；这可能是错误的..):

 for (int i = 0; i <= Xcoordinates.length; i++) { //loop through array 
     compare values, and determine outlier
     int lowestXValue = [find lowest x value]
     int highestXValue = [find highest x value; not outlier] }

     remove xcoordinates[outlier]
     remove ycoordinates[outlier]     

 int xLength = highestXValue - lowestXValue - 1 // -1 because can be on line

 for (int i = 0; i <= Ycoordinates.length; i++) { //loop through y array
      int lowestYValue = [find lowest y value]
      int highestYValue = [find highesy Y value] }

 int yLength = highestYValue - lowestYValue - 1;

 int boxArea = yLength * xLength

 System.out.println(boxArea);

---

但是，这只会搜索可能的 X 离群值，如果有一个 Y 值可以通过移除来最小化区域，它就不会捕捉到那个

Answer 1

我会创建两个排序的整数列表，一个用于 x 坐标，一个用于 y 坐标。然后您可以通过删除最大 x 坐标来检查保存的区域(保存的区域应该是最大 y 坐标时间(最大 x 坐标 - 第二高 x 坐标))。您可以通过删除最大 y 坐标来执行相同的操作来检查节省的区域，以较大者为最终答案。