http://acm.hdu.edu.cn/showproblem.php?pid=5128
题意：给定N个点，选出其中8个点组成两个矩形，使得两个矩形的面积和最大。
思路：找出所有的矩形，然后枚举，挑选求中的两个矩形，判断位置关系，符合条件求出他们的和最大值。坑点：可以内含，内含的时候计算外面的矩形的面积。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; int n;
struct node
{
int x,y;
bool operator <(const node &a) const
{
return (x<a.x)||(x==a.x&&y<a.y);
}
} p[],q[],f1[],f2[]; struct node1
{
int num[];
} c[]; int main()
{
//freopen("sss.txt","w",stdout);
while(scanf("%d",&n)!=EOF)
{
if(n==) break; for(int i=; i<=n; i++)
{
scanf("%d %d",&p[i].x,&p[i].y);
}
if(n<)
{
printf("imp\n");
continue;
}
sort(p+,p+n+);
int t1=;
for(int i=; i<=n; i++)
{
for(int j=; j<=n; j++)
{
if(i==j) continue;
for(int a=; a<=n; a++)
{
if(i==a||j==a) continue;
for(int b=; b<=n; b++)
{
if(i==b||j==b||a==b) continue;
q[]=p[i];
q[]=p[j];
q[]=p[a];
q[]=p[b];
sort(q,q+);
if(q[].x!=q[].x||q[].y!=q[].y||q[].x!=q[].x||q[].y!=q[].y)
{
continue;
}
if(q[].x!=q[].x&&q[].y!=q[].y)
{
c[t1].num[]=i;
c[t1].num[]=j;
c[t1].num[]=a;
c[t1++].num[]=b;
}
}
}
}
}
int ans=-;
for(int i=; i<t1; i++)
{
f1[]=p[c[i].num[]];
f1[]=p[c[i].num[]];
f1[]=p[c[i].num[]];
f1[]=p[c[i].num[]];
sort(f1,f1+);
for(int j=; j<t1; j++)
{
if(i==j) continue;
f2[]=p[c[j].num[]];
f2[]=p[c[j].num[]];
f2[]=p[c[j].num[]];
f2[]=p[c[j].num[]];
sort(f2,f2+);
bool flag=false;
for(int ii=; ii<; ii++)
{
for(int jj=; jj<; jj++)
{
if(p[c[i].num[ii]].x==p[c[j].num[jj]].x&&p[c[i].num[ii]].y==p[c[j].num[jj]].y)
{
flag=true;
break;
}
}
if(flag) break;
}
if(flag) continue;
if(f1[].x<=f2[].x&&f2[].x<=f1[].x&&f2[].y<=f1[].y&&f2[].y>=f1[].y&&f2[].x>=f1[].x)
{
continue;
}
if(f1[].x<=f2[].x&&f2[].x<=f1[].x&&f2[].y<=f1[].y&&f2[].y>=f1[].y&&f2[].x>=f1[].x)
{
continue;
}
if(f1[].x>=f2[].x&&f1[].x<=f2[].x&&f1[].y<=f2[].y&&f1[].y>=f2[].y&&f1[].x>=f2[].x)
{
continue;
}
if(f1[].x>=f2[].x&&f1[].x<=f2[].x&&f1[].y<=f2[].y&&f1[].y>=f2[].y&&f1[].x>=f2[].x)
{
continue;
}
if(f1[].x<=f2[].x&&f2[].x<=f1[].x&&f2[].y<=f1[].y&&f2[].y>=f1[].y&&f2[].y<=f1[].y)
{
continue;
}
if(f1[].x<=f2[].x&&f2[].x<=f1[].x&&f2[].y>=f1[].y&&f2[].y<=f1[].y&&f2[].y>=f1[].y)
{
continue;
}
if(f2[].x<=f1[].x&&f1[].x<=f2[].x&&f1[].y<=f2[].y&&f1[].y>=f2[].y&&f1[].y<=f2[].y)
{
continue;
}
if(f2[].x<=f1[].x&&f1[].x<=f2[].x&&f1[].y>=f2[].y&&f1[].y<=f2[].y&&f1[].y>=f2[].y)
{
continue;
}
int s=-;
if(f1[].x>f2[].x&&f1[].x<f2[].x&&f1[].y>f2[].y&&f1[].y<f2[].y)
{
s=(f2[].y-f2[].y)*(f2[].x-f2[].x);
}
else if(f2[].x>f1[].x&&f2[].x<f1[].x&&f2[].y>f1[].y&&f2[].y<f1[].y)
{
s=(f1[].y-f1[].y)*(f1[].x-f1[].x);
}
else
s=(f1[].y-f1[].y)*(f1[].x-f1[].x)+(f2[].y-f2[].y)*(f2[].x-f2[].x);
ans=max(ans,s);
}
}
if(ans==-) printf("imp\n");
else
printf("%d\n",ans);
}
return ;
}