笔试刷题-百度2018-06-23

题目描述：

/**
度度熊有一张网格纸，但是纸上有一些点过的点，每个点都在网格点上，
若把网格看成一个坐标轴平行于网格线的坐标系的话，每个点可以用一对整数x，y来表示。
度度熊必须沿着网格线画一个正方形，使所有点在正方形的内部或者边界。
然后把这个正方形剪下来。问剪掉正方形的最小面积是多少。
输入描述:
第一行一个数n(2≤n≤1000)表示点数，接下来每行一对整数xi,yi(－1e9<=xi,yi<=1e9)表示网格上的点

输出描述:
一行输出最小面积

输入例子1:
2
0 0
0 3

输出例子1:
9
*/

思路如下：

题目由于要求了正方形的边都要平行于x 、y轴
那么正方形的最小边长为max(maxX-minX, maxY-minY)

代码如下：

#include<stdio.h>
#include<iostream>
#include<climits>
#include<algorithm>

#define MAX_N 1005

using namespace std;

int x[MAX_N], y[MAX_N];

//找最大间隔时间复杂度是O(n)只需要记录之前一段的两个端点并更新就可以了
//排序复杂度O(nlgn)
//直接穷举O(n^2)
int main()
{
    int n;
    while(scanf("%d", &n)==1)
    {
        int max_dx=INT_MIN, max_dy=INT_MIN;
        for(int i=0; i<n; i++)
            scanf("%d%d", x+i, y+i);
        sort(x, x+n);
        sort(y, y+n);
        max_dx=x[n-1]-x[0];
        max_dy=y[n-1]-y[0];
        int d=max(max_dx, max_dy);
        long long s=(long long)d*(long long)d;
        printf("%lld\n", s);
    }
    return 0;
}