The E-pang Palace(暴力几何)

The E-pang Palace(暴力几何)

//暴力的几何题,问,n个点可以组成的矩形,不相交,可包含的情况下,最大的面积,还有就是边一定与 x y 轴平行,所以比较简单了

//暴力遍历对角线,搜出所有可能的矩形,然后二重循环所有矩形,判断一下,输出最大即可

 #include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
using namespace std;
#define MX 35
struct Mat
{
int a,b,c,d;
int area;
}mat[]; int n;
int x[MX];
int y[MX];
int G[][]; int check(int u,int v)
{
int xxx = min(min(x[mat[u].a],x[mat[u].b]),min(x[mat[u].c],x[mat[u].d]));
int xxy = min(min(y[mat[u].a],y[mat[u].b]),min(y[mat[u].c],y[mat[u].d]));
int ddx = max(max(x[mat[u].a],x[mat[u].b]),max(x[mat[u].c],x[mat[u].d]));
int ddy = max(max(y[mat[u].a],y[mat[u].b]),max(y[mat[u].c],y[mat[u].d])); int xx = min(min(x[mat[v].a],x[mat[v].b]),min(x[mat[v].c],x[mat[v].d]));
int xy = min(min(y[mat[v].a],y[mat[v].b]),min(y[mat[v].c],y[mat[v].d]));
int dx = max(max(x[mat[v].a],x[mat[v].b]),max(x[mat[v].c],x[mat[v].d]));
int dy = max(max(y[mat[v].a],y[mat[v].b]),max(y[mat[v].c],y[mat[v].d])); if (xxx>dx||xxy>dy||ddx<xx||ddy<xy)//在 右上左下
return mat[v].area+mat[u].area; if (xxx>xx&&ddx<dx&&xxy>xy&&ddy<dy)//包含
return max(mat[v].area,mat[u].area);
if (xxx<xx&&ddx>dx&&xxy<xy&&ddy>dy)
return max(mat[v].area,mat[u].area); return ;
} int main()
{
while (scanf("%d",&n)&&n)
{
memset(G,-,sizeof(G));
for (int i=;i<n;i++)
{
scanf("%d%d",&x[i],&y[i]);
G[x[i]][y[i]]=i;
}
int m=;
for (int i=;i<n;i++)
{
for (int j=i+;j<n;j++)
{
if (x[i]==x[j]||y[i]==y[j]) continue;
int fir,sec;
if (G[x[i]][y[j]]!=-) fir=G[x[i]][y[j]];
else continue;
if (G[x[j]][y[i]]!=-) sec=G[x[j]][y[i]];
else continue; int lon=abs(x[i]-x[j]);
int kua=abs(y[i]-y[j]);
mat[m++]=(Mat){fir,sec,i,j,lon*kua};
}
}
int ans = ;
for (int i=;i<m;i++)
{
for (int j=i+;j<m;j++)
{
ans = max(ans,check(i,j));
}
}
if (ans!=)
printf("%d\n",ans);
else
printf("imp\n");
}
return ;
}
上一篇:IIS发布,无法显示CSS样式和图片


下一篇:Order by排序