农田缩减

题目

链接：1826. 农田缩减 - AcWing题库

农夫约翰的 N 头奶牛分布在其二维农场的不同位置。

约翰想用一个长方形的围栏把所有的奶牛围起来，围栏的边需要平行于 x 轴和 y 轴。

在能够包含所有奶牛的情况下（处于围栏边界的奶牛也算包含在内），约翰希望围栏围起的面积尽可能小。

不幸的是，由于上个季度的牛奶产量很低，约翰的预算十分紧张。

因此，他希望建立一个更小的围栏，甚至为了实现这一目标，他愿意卖掉农场中的一头奶牛。

请帮助约翰计算，卖掉牛群中的一头奶牛以后，他可以用围栏围起来的最小面积（为剩下的奶牛建造尽可能小的围栏）。

对于这个问题，请将奶牛视为点，将围栏视为四个线段的集合。

注意，答案可以是零，例如，所有剩余的奶牛最终都站在同一条垂直或水平线上。

代码

import java.util.*;


public class Main {
    static int N = 100010;
    static int n, x, y;
    static node min_x, premin_x;
    static node max_x, premax_x;
    static node min_y, premin_y;
    static node max_y, premax_y;
    public static void minx(int x, int key)
    {
        if(x < min_x.v)
        {
            premin_x.key = min_x.key;
            premin_x.v = min_x.v;
            min_x.key = key;
            min_x.v = x;
        }
        else if(x < premin_x.v)
        {
            premin_x.key = key;
            premin_x.v = x;
        }
    }
    public static void maxx(int x, int key)
    {
        if(x > max_x.v)
        {
            premax_x.key = max_x.key;
            premax_x.v = max_x.v;
            max_x.key = key;
            max_x.v = x;
        }
        else if(x > premax_x.v)
        {
            premax_x.key = key;
            premax_x.v = x;
        }
    }
    public static void miny(int y, int key)
    {
        if(y < min_y.v)
        {
            premin_y.key = min_y.key;
            premin_y.v = min_y.v;
            min_y.key = key;
            min_y.v = y;
        }
        else if(y < premin_y.v)
        {
            premin_y.key = key;
            premin_y.v = y;
        }
    }
    public static void maxy(int y, int key)
    {
        if(y > max_y.v)
        {
            premax_y.key = max_y.key;
            premax_y.v = max_y.v;
            max_y.key = key;
            max_y.v = y;
        }
        else if(y > premax_y.v)
        {
            premax_y.key = key;
            premax_y.v = y;
        }
    }
    public static void main(String[] args) {
        Scanner inScanner = new Scanner(System.in);
        n = inScanner.nextInt();
        min_x = new node(0, Integer.MAX_VALUE);
        premin_x = new node(0, Integer.MAX_VALUE);
        min_y = new node(0, Integer.MAX_VALUE);
        premin_y = new node(0, Integer.MAX_VALUE);

        max_x = new node(0, Integer.MIN_VALUE);
        premax_x = new node(0, Integer.MIN_VALUE);
        max_y = new node(0, Integer.MIN_VALUE);
        premax_y = new node(0, Integer.MIN_VALUE);
        for(int i = 1; i <= n; i ++)
        {
            x = inScanner.nextInt();
            y = inScanner.nextInt();
            minx(x, i);
            miny(y, i);
            maxx(x, i);
            maxy(y, i);
        }
        inScanner.close();
        int lx = premin_x.v - min_x.v;
        int rx = max_x.v - premax_x.v;
        int ly = premin_y.v - min_y.v;
        int ry = max_y.v - premax_y.v;
        if(lx >= rx && lx >= ly && lx >= ry)
        {
            if(min_x.key == min_y.key)
                min_y.v = premin_y.v;
            else if(min_x.key == max_y.key)
                max_y.v = premax_y.v;
            min_x.v = premin_x.v;
        }
        else if(rx >= lx && rx >= ly && rx >= ry)
        {
            if(max_x.key == min_y.key)
                min_y.v = premin_y.v;
            else if(max_x.key == max_y.key)
                max_y.v = premax_y.v;
            max_x.v = premax_x.v;
        }
        else if(ly >= lx && ly >= rx && ly >= ry)
        {
            if(min_y.key == min_x.key)
                min_x.v = premin_x.v;
            else if(min_y.key == max_x.key)
                max_x.v = premax_x.v;
            min_y.v = premin_y.v;
        }
        else
        {
            if(max_y.key == min_x.key)
                min_x.v = premin_x.v;
            else if(max_y.key == max_x.key)
                max_x.v = premax_x.v;
            max_y.v = premax_y.v;
        }
        System.out.println((max_x.v - min_x.v) * (max_y.v - min_y.v));
    }
}
class node
{
    int v, key;
    public node(int key, int v)
    {
        this.v = v;
        this.key = key;
    }
}