Uva11134
2024-08-23 14:50:33
#include<bits/stdc++.h> #define inf 0x3f3f3f3f const int maxn=; using namespace std; int n; struct rook{
int x1,y1;
int x2,y2;
int id;
int resx,resy;
int size(){
return abs(x1 - x2) * abs(x1 - x2) + abs(y1 - y2) * abs(y1 - y2);
}
int width(){
return abs(x1 - x2);
}
int len(){
return abs(y1 - y2);
}
}rooks[maxn+]; int flagx[maxn+]; int flagy[maxn+]; bool cmpx(rook a, rook b){
/*if(a.width() == b.width()){
return a.x1 < b.x1;
}
return a.width() < b.width();*/
//刚开始想错了,这么去贪心,是错的。
/* 反例
* 1111
* 1
* 1
* 1
* 11
*/
if(a.x2 == b.x2){
return a.x1 < b.x1;
}
return a.x2 < b.x2;
}
bool cmpy(rook a, rook b){
/*if(a.len() == b.len()){
return a.y1 < b.y1;
}
return a.len() < b.len();*/
if(a.y2 == b.y2){
return a.y1 < b.y1;
}
return a.y2 < b.y2;
}
bool cmp1(rook a, rook b){
return a.id < b.id;
} int main()
{
while(scanf("%d",&n)!=EOF&&n){
int res = ;
memset(flagx, , sizeof(flagx));
memset(flagy, , sizeof(flagy));
for(int i = ; i < n; ++i){
scanf("%d%d%d%d",&rooks[i].x1,&rooks[i].y1,&rooks[i].x2,&rooks[i].y2);
rooks[i].id = i;
}
sort(rooks, rooks + n, cmpx);
for(int i = ; i < n; ++i){
int flag = ;
for(int j = rooks[i].x1; j <= rooks[i].x2; ++j){
if(!flagx[j]){
flagx[j] = ;
rooks[i].resx = j;
flag = ;
break;
}
}
if(!flag){
res = ;
break;
}
}
if(!res){
sort(rooks, rooks + n, cmpy);
for(int i = ; i < n; ++i){
int flag = ;
for(int j = rooks[i].y1; j <= rooks[i].y2; ++j){
if(!flagy[j]){
flagy[j] = ;
rooks[i].resy = j;
flag = ;
break;
}
}
if(!flag){
res = ;
break;
}
}
}
if(res){
printf("IMPOSSIBLE\n");
} else {
sort(rooks, rooks + n, cmp1);
for(int i = ; i < n; ++i){
printf("%d %d\n",rooks[i].resx,rooks[i].resy);
}
}
}
return ;
}
最新文章
- [原创]在Linux系统Ubuntu14.04上安装部署docker。
- Python 基礎 - 元組與簡易購物車實做
- HDU 5446 中国剩余定理+lucas
- Code::Blocks配置GTK+2和GTK+3
- 安装win10
- MVC 基架不支持 Entity Framework 6 或更高版本
- Java提高篇——通过分析 JDK 源代码研究 Hash 存储机制
- HDU 4568 Hunter 最短路+状压DP
- [SAP ABAP开发技术总结]搜索帮助Search Help (F4)
- #数据结构-fib
- C#读取shp的属性信息
- bzoj 4300: 绝世好题 dp
- 【原创】poj ----- 2524 Ubiquitous Religions 解题报告
- ExecutorService的submit(Runnable x)和execute(Runnable x) 两个方法的本质区别
- unbtun python tab补全
- 转:微信开发之使用java获取签名signature(贴源码,附工程)
- 带以太网的MicroPython开发板:TPYBoardv201温湿度上传实例
- Spring的事务初见
- HTML与盒模型
- tp5自定义分页参数
热门文章
- html5--1.8超链接下
- html5--1.4元素的属性
- 线程池ThreadPool的常用方法介绍
- Mybatis异常_02_Result Maps collection already contains value for
- 洛谷 P3804 [模板] 后缀自动机
- The specified named connection is either not found in the configuration, not intended to be used
- JavaScript:Map使用
- docker学习 (二)基本概念
- Poco 编译mysql
- MSSQl分布式查询(转)