POJ 3168 排序+扫描
2024-08-31 08:08:53
题意:
思路:
我们可以把每个矩形拆成四条线
与x轴平行的放在一起
与y轴平行的放在一起
排个序 判一判有没有交 有交 则说明不可扩张 统计一下 就可以了
处理的姿势很重要
姿势不对毁一生
//By SiriusRen
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 55555
int n,x1,y1,x2,y2,cnt,vis[N],ans,maxx;
struct Edgex{int x,y1,y2,id;bool operator < (const Edgex &a)const{if(x!=a.x)return x<a.x;return y2<a.y2;}}edgex[N];
struct Edgey{int y,x1,x2,id;bool operator < (const Edgey &a)const{if(y!=a.y)return y<a.y;return x1<a.x1;}}edgey[N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d%d%d",&x1,&y1,&x2,&y2),vis[i]=1,
edgex[++cnt].x=x1,edgex[cnt].y1=y2,edgex[cnt].y2=y1,edgex[cnt].id=i,
edgey[cnt].y=y1,edgey[cnt].x1=x1,edgey[cnt].x2=x2,edgey[cnt].id=i,
edgex[++cnt].x=x2,edgex[cnt].y1=y2,edgex[cnt].y2=y1,edgex[cnt].id=i,
edgey[cnt].y=y2,edgey[cnt].x1=x1,edgey[cnt].x2=x2,edgey[cnt].id=i;
sort(edgex+1,edgex+1+cnt),sort(edgey+1,edgey+1+cnt);
for(int i=1,j=i;i<=cnt;i=j,maxx=edgex[i].y1){
while(edgex[i].x==edgex[j].x)j++;
for(int k=i+1;k<j;k++){
if(edgex[k].y2<=maxx)vis[edgex[k].id]=vis[edgex[k-1].id]=0;
maxx=max(maxx,edgex[k].y1);
}
}
for(int i=1,j=i;i<=cnt;i=j,maxx=edgey[i].x2){
while(edgey[i].y==edgey[j].y)j++;
for(int k=i+1;k<j;k++){
if(edgey[k].x1<=maxx)vis[edgey[k].id]=vis[edgey[k-1].id]=0;
maxx=max(maxx,edgey[k].x2);
}
}
for(int i=1;i<=n;i++)ans+=vis[i];
printf("%d\n",ans);
}
最新文章
- html中表格元素的相关总结
- MVC4 使用概述
- 烂泥:KVM快照的创建与恢复
- linux安装IPython四种方法
- TatukGIS - GisDefs - DateTimeToXMLString 函数
- 最小生成树 10.1.5.253 1505 poj 1258 http://poj.org/problem?id=1258
- SVN基础命令手册
- Debian 8 安装BtSync
- ckeditor上传图片的注意点
- 结对编程1-基于GUI的四则运算生成器
- MongoDB安装(windows 10环境)
- linux下删除.svn的方法
- oracle远程连接服务器数据库
- 浅谈SQL注入
- ubuntu 下使用 jsoncpp库
- UVALive 4725 Airport(二分)
- 如何安装 Microsoft Office 兼容包,以便您可以在早期版本的 Microsoft Office 中打开和保存 Office Open XML 格式
- HTML-入门篇day01
- web http协议
- 多网卡下,vlc发送IGMP组播报告包
热门文章
- Java 类和对象12
- 有关 IE11
- Nordic Collegiate Programming Contest 2015​(第七场)
- MD5工具类-详细
- inceptionnet
- LightOJ-1341 Aladdin and the Flying Carpet 分解质因数(注意对大素数的优化)
- 「BZOJ3343」教主的魔法(分块+二分查找)
- 【 Beginning iOS 7 Development《精通iOS7开发》】05 Autorotation and Autosizing
- [React] Implement a Higher Order Component with Render Props
- HDU 2444 The Accomodation of Students 二分图判定+最大匹配