You are given N 2D points P1, P2, ... PN. If there is a rectangle satisfying that its 4 vertices are in the given point set and its 4 sides are parallel to the axis we say the rectange exists.
Find the smallest exsisting rectange and output its area.
The first line contains an integer N. (1 <= N <= 1000)
The following N lines each contain 2 integers Xi and Yi denoting a point (Xi, Yi). (0 <= Xi, Yi <= 1000000)
Output the smallest area. If no rectangle exsists output -1.
样例输入 9 0 0 0 1 0 4 1 0 1 1 1 4 4 0 4 1 4 4 样例输出 1 思路：枚举任意2点作为矩形对角线上的2点，然后判断其另2个点是否存在即可。点坐标可以用map存下。 #include<bits/stdc++.h> using namespace std; struct Point { int x,y; }p[2000]; map<pair<int,int>,int>ma; int main() { int n; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d%d",&p[i].x,&p[i].y); ma[make_pair(p[i].x,p[i].y)]=1; } long long ans=1e15+7; for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { if(p[i].y==p[j].y)continue; if(p[i].x==p[j].x)continue; if(ma[make_pair(p[i].x,p[j].y)]&&ma[make_pair(p[j].x,p[i].y)]) { ans=min(ans,(long long)abs(p[i].x-p[j].x)*(long long)abs(p[i].y-p[j].y)); } } } if(ans>=1e15+7)ans=-1; cout<<ans<<endl; return 0; }
