http://acm.hdu.edu.cn/showproblem.php?pid=5128

给出n个点,求n个点组成两个矩形的最大面积.

矩形必须平行x轴,并且不能相交,但是小矩形在大矩形内部是可以的,面积就为大矩形的面积.

我是枚举一条对角线,然后去找另外两个点是否在坐标中存在这样就可以确定一个矩形,

同理可以枚举出另外有一个矩形,但是要注意坐标不能重复,

判断矩形相交的话,只要判断一个矩形的4个点是否有在另一个矩形的范围内即可.

 #include<cstdio>
#include<cstring>
#include<set>
#include<iostream>
#include<algorithm>
using namespace std;
struct point
{
int x,y;
bool operator < (const point a) const
{
return x==a.x?y<a.y:x<a.x;
}
}p[],q1,q2,q3,q4; int check(point a,point b,point c) //注意区分是在矩形内部还是在矩形边上
{
if(a.x>=b.x&&a.x<=c.x&&a.y>=c.y&&a.y<=b.y)
{
if(a.x>b.x&&a.x<c.x&&a.y>c.y&&a.y<b.y) return ;
return ;
}
return -;
}
int main()
{
//freopen("a.txt","r",stdin);
int n,area;
while(~scanf("%d",&n)&&n)
{
if(n<) {printf("imp\n");continue;}
set<point>s;
// set<point>::iterator it;
int maxn=,cnt=;
for(int i=;i<=n;i++)
{
scanf("%d%d",&p[i].x,&p[i].y);
s.insert(p[i]);
}
sort(p+,p+n+);
/*for(it=s.begin();it!=s.end();it++)
{
point t=*it;
printf("%d %d\n",t.x,t.y);
}*/
for(int i=;i<=n;i++)
{
for(int j=i+;j<=n;j++)
{
if(p[i].x<p[j].x&&p[i].y<p[j].y) //枚举出第一个矩形
{
q1.x=p[i].x;q1.y=p[j].y;
if(!s.count(q1))continue;
q2.x=p[j].x;q2.y=p[i].y;
if(!s.count(q2))continue;
for(int l=;l<=n;l++)
{
for(int k=l+;k<=n;k++)
{
if(p[l].x<p[k].x&&p[l].y<p[k].y)//第二个矩形
{
q3.x=p[l].x;q3.y=p[k].y;
if(!s.count(q3))continue;
q4.x=p[k].x;q4.y=p[l].y;
if(!s.count(q4))continue;
if(i==l||j==l||i==k||j==k)continue; //防止坐标重复
if(q3.x==p[i].x&&q3.y==p[i].y||q3.x==p[j].x&&q3.x==p[j].y) continue;
if(q4.x==p[i].x&&q4.y==p[i].y||q4.x==p[j].x&&q4.x==p[j].y) continue; int x1=check(p[i],q3,q4);
int x2=check(p[j],q3,q4);
int x3=check(q1,q3,q4);
int x4=check(q2,q3,q4); //判断在矩形内部还是边界
if(x1==&&x2==&&x3==&&x4==) //内含
{
// printf("%d %d %d %d\n",q1.x,q1.y,q2.x,q2.y);
area=abs(q4.x-q3.x)*abs(q3.y-q4.y);
if(area>maxn) maxn=area;
//printf("%d\n",area);
cnt=;
}
else if(x1==||x2==||x3==||x4==)continue; //相交
else if(x1==-&&x2==-&&x3==-&&x4==-) //枚举 另一种情况
{
//printf("%d\n",1);
int y1=check(p[l],q1,q2);
int y2=check(p[k],q1,q2);
int y3=check(q3,q1,q2);
int y4=check(q4,q1,q2);
//printf("%d\n",ans);
// printf("%d %d %d %d\n",q1.x,q1.y,q2.x,q2.y);
// printf("%d %d %d %d\n",q3.x,q3.y,q4.x,q4.y);
if(y1==||y2==||y3==||y4==) continue;
else if(y1==&&y2==&&y3==&&y4==)
{
area=abs(q2.x-q1.x)*abs(q1.y-q2.y);
if(area>maxn) maxn=area;
cnt=;
}
else if(y1==-&&y2==-&&y3==-&&y4==-)
{
// printf("%d %d %d %d\n",q1.x,q1.y,q2.x,q2.y);
//printf("%d %d %d %d\n",q3.x,q3.y,q4.x,q4.y);
area=abs(q2.x-q1.x)*abs(q1.y-q2.y)+abs(q4.x-q3.x)*abs(q3.y-q4.y);
// printf("%d\n",area);
if(area>maxn) maxn=area;
cnt=;
}
}
}
}
}
}
}
}
if(!cnt) printf("imp\n");
else
printf("%d\n",maxn);
}
return ;
}

最新文章

  1. Redis数据结构详解(一)
  2. iredmail安装脚本分析(三)---conf/global DISTRO值的来源及操作系统的判断
  3. 苹果官方制作MAC OS的启动U盘的步骤
  4. [开源]jquery-ajax-cache:快速优化页面ajax请求,使用localStorage缓存请求
  5. [Apio2014]回文串
  6. c风格字符串函数
  7. 更新代码和工具,组织起来,提供所有博文(C++,2014.09)
  8. 在PHP中连接数据库的八大步骤
  9. ORACLE EBS常用表及查询语句(最终整理版)
  10. shared_ptr和动态数组
  11. face_recognition 模块安装
  12. Linux 文件查找命令详解
  13. 序列化模块和sys模块
  14. 用Javascript,DHTML控制表格的某一列的显示与隐藏
  15. VMware Ubuntu 虚拟机安装 VMwareTools (VMware虚拟机如何与主机互相复制文件)
  16. 深入探讨JavaScript如何实现深度复制(deep clone)
  17. 安装 telnet
  18. DOM3级的变化
  19. sublime text3 当运行报错error时,取消显示路径path的方法
  20. Eclipse导入项目时出错提示 project is missing required library

热门文章

  1. Azure PowerShell 在ARM环境下使用指定 vhd(本地化后的磁盘) 来创建虚拟机
  2. Data Center Manager Leveraging OpenStack
  3. CATransaction 知识
  4. 善用Object.defineProperty巧妙找到修改某个变量的准确代码位置
  5. macos openssl 生成rsa证书 -mark
  6. linux之awk命令
  7. golang结构体排序 - 根据下载时间重命名本地文件
  8. JS将时间戳转换为刚刚、N分钟前、今天几点几分、昨天几点几分等表示法
  9. es6数组新特性
  10. sqlserver差异备份3117