Java 2D 最小化

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();
        }

Answer 1

让您拥有4分(2 4)、(1 1)、(5 2)、(17 25)。 由于您总是可以删除一个点来优化区域，因此，有 C(4,3) 种可能的点组合，它们是:

{ { (2 4), (1 1), (5 2) }, { (1 1), (5 2), ( 17 25) }, { (2 4), (5 2),(17 25) }, { (2 4),(1 1),(17 25 ) } }

<小时/>

您可以找到的一组最小区域为:

(Max(所有 x 坐标)-Min(所有 x 坐标)) * (Max(所有 y 坐标) 坐标)-Min(所有 y 坐标))

<小时/>

1. { (2 4), (1 1), (5 2) }

   该组的最小面积等于(5-1)*(4-1) = 4*3 = 12

2. { (1 1), (5 2), (17 25) }

   您可以找到该组的最小面积为:(17-1)*(25-1) = 16*24 = 384

3. { (2 4), (5 2), (17 25) }

   您可以找到该组的最小面积为:(17-2)*(25-2) = 15*23 = 345

4. { (2 4),(1 1),(17 25) }

   您可以找到该组的最小面积为:(17-1)*(25-1) = 16*24 = 384

<小时/>

在集合{ (2 4), (1 1), (5 2) }的所有区域中，最小值等于 12 ，所以所需的答案是12。