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