Codeforces | CF1028C 【Rectangles】
2024-08-30 00:01:58
(这道题太简单啦...虽说我锤了一上午都没过...我能说这道题和\(CF1029C\)算是同一道题吗...)
按照时间顺序来说...\(CF1029\)在\(CF1028\)前面(而且\(CF1029\)还是\(Div3\)),前后没差多长时间就惊现高相似度题目(所以CF是有多迫切想让大家上分)
CF1029C传送门
两道题的唯一差别就是一个是一维,一个是二维(我是不是应该猜一下\(CF1036C\)会出一个三维的),都是范围覆盖,和\(CF1029C\)一样,只需要确定最严格的边界限制,题目要求输出任意一个在至少\(n-1\)个矩形内的点,也即可以删去一个矩形,输出剩下\(n-1\)个矩形的交集内的任意点(在此直接选用交集左下角的点)
根据题目条件,一定存在一些满足条件的点,所以删去的矩形应该是与其他\(n-1\)个矩形的交集没有公共部分的矩形,所以和\(CF1029C\)中的处理方式相似,在造成最严格限制的至多四个矩形中枚举删除即可,若删除后剩下的\(n-1\)个矩形交集不为空即可输出答案(如果\(n\)个矩形的交集不为空可以不删除)
下面放代码\(\downarrow\downarrow\downarrow\)
#include<cstdio>//CF1028C
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<queue>
using namespace std;
int n;
struct lborder{
int x,id;
bool operator<(const lborder&rhs)const{
return x<rhs.x;
}
};
struct rborder{
int x,id;
bool operator<(const rborder&rhs)const{
return x>rhs.x;
}
};
lborder lbx,lby;rborder rbx,rby;
priority_queue<lborder>ql[2];
priority_queue<rborder>qr[2];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d%d%d",&lbx.x,&lby.x,&rbx.x,&rby.x);
lbx.id=rbx.id=lby.id=rby.id=i;
ql[0].push(lbx);
qr[0].push(rbx);
ql[1].push(lby);
qr[1].push(rby);
}
int id[2][4],x[2][4];
id[0][0]=ql[0].top().id;id[0][1]=ql[1].top().id;
id[0][2]=qr[0].top().id;id[0][3]=qr[1].top().id;
x[0][0]=ql[0].top().x;x[0][1]=ql[1].top().x;
x[0][2]=qr[0].top().x;x[0][3]=qr[1].top().x;
ql[0].pop();qr[0].pop();ql[1].pop();qr[1].pop();
id[1][0]=ql[0].top().id;id[1][1]=ql[1].top().id;
id[1][2]=qr[0].top().id;id[1][3]=qr[1].top().id;
x[1][0]=ql[0].top().x;x[1][1]=ql[1].top().x;
x[1][2]=qr[0].top().x;x[1][3]=qr[1].top().x;
int vis[4]={0,0,0,0},bor[4];
if(x[0][0]<=x[0][2]&&x[0][1]<=x[0][3]){
printf("%d %d\n",x[0][0],x[0][1]);
return 0;
}
for(int i=0;i<4;i++){
if(vis[i]){
continue;
}
vis[i]=1;
for(int j=0;j<4;j++){
if(j==i){
bor[j]=x[1][j];
}
else{
bor[j]=x[0][j];
}
}
for(int j=i+1;j<4;j++){
if(id[0][j]==id[0][i]){
bor[j]=x[1][j];
vis[j]=1;
}
}
if(bor[0]>bor[2]||bor[1]>bor[3]){
continue;
}
else{
printf("%d %d\n",bor[0],bor[1]);
return 0;
}
}
return 0;
}
最新文章
- Java多线程 2 线程的生命周期和状态控制
- sublime text常用快捷键
- jQuery切换网页皮肤保存到Cookie实例
- ORA-29275: partial multibyte character
- RGB颜色中的参数是变量的时候,为什么要加上两个+号在左右?
- Http协议中的Content-Length属性
- SpringMVC整合Shiro
- 2016年12-09php函数
- sybaseIQ索引类型和使用注意事项
- DIV+CSS设计IE6浮动产生双倍距离
- Hadoop开发遇到的问题之reduce卡住
- [luogu P1967][NOIp2013] 货车运输
- 2017-06-23(chmod whoami chown)
- dos2unix和unix2dos
- CF367 E - Working routine
- PL/SQL 加字段 修改数据库之后 之后记得保存脚本
- 数据类型&;字符串得索引及切片
- python 基本语句
- postgresql 窗口函数排序实例
- PCP项目立项