离散化处理。判断建筑可见性比较麻烦。下面采用离散化解决:把所有的x坐标排序去重,在相邻两个x坐标表示的区间中,整个区间要么同时可见,要么同时不可见。如何判断该区间是否可见?具体做法是选取该区间中点坐标x=mx来做代表,判断mx是否可见。那么判断该监周屋是否在点mx0可见?首先该建筑物必须包含该点,并且在他南边的包含该点的建筑物不能比它高。

//--------离散化处理技巧
//----------------------
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn = 100+ 5; struct Building{
int id;
double x, y, w, l, h;
bool operator<(Building m){
if (m.x == x)return y < m.y;
else return x < m.x;
} } b[maxn]; double x[2 * maxn];
int n,m; //判断下标为i的建筑物在x=mx处是否覆盖
bool cover(int i, double mx){
return mx<b[i].x + b[i].w&&mx>b[i].x;
} //判断建筑物是否在mx处可见
bool isVision(int i, double mx){
if (!cover(i, mx))return false;
//判断它南边是否有建筑物覆盖该点
for (int k = 0; k < n; k++){
if (b[k].y<b[i].y&&b[k].h>=b[i].h&&cover(k, mx))
return false;
}
return true;
}
int main(){
int kase = 1;
while (scanf("%d", &n) && n){
for (int i = 0; i < n; i++){
scanf("%lf%lf%lf%lf%lf",&b[i].x, &b[i].y, &b[i].w, &b[i].l, &b[i].h);
b[i].id = i + 1;
x[2 * i] = b[i].x, x[2 * i + 1] = b[i].x + b[i].w;
}
sort(b, b + n);
sort(x, x + 2 * n);
//去重复
m = unique(x, x + 2*n) - x; vector<int>v;
int j;
for (int i = 0; i < n; i++){
//枚举每一个mx
for (j = 0; j < m - 1; j++){
if (isVision(i, (x[j] + x[j + 1]) / 2))
break; //一旦遇到当前建筑物在该点可见则跳出循环
}
if (j<m-1)v.push_back(b[i].id);
}
if (kase>1)printf("\n");
printf("For map #%d, the visible buildings are numbered as follows:\n", kase++);
printf("%d", v[0]);
for (int i = 1; i < v.size(); i++)printf(" %d", v[i]);
printf("\n");
}
return 0;
}

  

最新文章

  1. 如何得到自定义UITableViewCell中的按钮所在的cell的indexPath.row
  2. 深入浅出ExtJS 第六章 布局
  3. 解读XMP元数据中ALAssetRepresentation
  4. 用ContentProvider向系统增加联系人
  5. JUnit单元测试框架的使用
  6. javascript 全选与反选
  7. House Robber &amp; House Robber II
  8. [转]What is a WebRTC Gateway anyway? (Lorenzo Miniero)
  9. 三分钟明白 Activiti工作流 -- java运用
  10. npm 是node.js下带的一个包管理工具
  11. 前端开发【第二篇: css】
  12. SpringSecurity身份验证基础入门
  13. three.js 3d三维网页代码加密的实现方法
  14. 通过socket获取图片并保存
  15. Java面向对象----个人参考资料
  16. Getting Started with Processing 第二,三章总结
  17. ASP.NET AJAX入门系列(9):在母版页中使用UpdatePanel
  18. COCI 2018/2019 CONTEST #2 Solution
  19. win 安装pip和requests
  20. 如何确定拍照时,相机屏幕是横屏or竖屏?

热门文章

  1. Centos安装后的一些必要处理工作
  2. Python列表及元组操作
  3. linux shell常用语法
  4. c#网络编程-第一章
  5. 插件 原生js 省市区 三级联动 源码
  6. snmp 默认团体名检测利用
  7. linux中高端内存和低端内存的概念【转】
  8. (九)ubuntu解决resolv.conf被重写问题
  9. BufferedInputStream&amp;BufferedOutputStream
  10. 二十六个月Android学习工作总结【转】