题目描述:
/**
度度熊有一张网格纸,但是纸上有一些点过的点,每个点都在网格点上,
若把网格看成一个坐标轴平行于网格线的坐标系的话,每个点可以用一对整数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;
}
网友评论