链接：http://codeforces.com/gym/101116
题意：给出n个点，要求一个矩形框将（n/2）+1个点框住，要面积最小
解法：先根据x轴选出i->j之间的点，中间的点(包括两边)按照y排序，固定一边X=(xj-xi),Y就枚举点两端的Y坐标，细节是注意要取（n/2）+1个点
事实上这样取里面一定符合要求
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
struct P
{
int x,y;
}H[10000],X[10000];
bool cmd1(P a,P b)
{
if(a.x==b.x)
{
return a.y<b.y;
}
else
{
return a.x<b.x;
}
}
bool cmd2(P a,P b)
{
if(a.y==b.y)
{
return a.x<b.x;
}
else
{
return a.y<b.y;
}
}
int main()
{
int t,n;
cin>>t;
while(t--)
{
int ans=(1<<31)-1;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>H[i].x>>H[i].y;
}
if(n==1)
{
cout<<"0"<<endl;
continue;
}
int num=n/2+1;
sort(H+1,H+n+1,cmd1);
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
int cot=0;
//枚举ij之间的点，按x坐标
for(int k=1;k<=n;k++)
{
if(H[k].x>=H[i].x&&H[k].x<=H[j].x)
{
// cout<<"A"<<endl;
X[++cot]=H[k];
}
}
sort(X+1,X+1+cot,cmd2);
for(int k=1;k<=cot;k++)
{
// cout<<X[k].y<<"A"<<endl;
}
int x1=H[i].x;
int x2=H[j].x;
// cout<<x1<<"B"<<x2<<endl;
for(int k=1;k<=cot-num+1;k++)
{
int y1=X[k].y;
int y2=X[k+num-1].y;
// cout<<y1<<"B"<<y2<<endl;
ans=min(ans,(x1-x2)*(y1-y2));
}
}
}
cout<<ans<<endl;
}
return 0;
}