这篇博客讲的蛮好 http://www.cnblogs.com/farewell-farewell/p/5330429.html 题意：给定了许多建筑的俯视图，每个建筑用左下角的下标，长度，宽度，高度。求正视图可以看到哪些建筑 分析：将所有建筑存下来，然后再按x从小到大，若x相同，就按照y从小到大。然后按照这个顺序扫一遍？怎么扫？ 然后这里用的是离散化，因为枚举坐标范围太大了，然后我可以用离散化，将无限变有限。怎么变有限？将图上的所有x坐标排序去重，则在x相邻区间内，要么有房子，要么没有。这样的话我们只用在这个区间内取一个点，然后看我们判断的房子是不是包含这个，然后前面有没有房子阻拦的即可
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> #include <cmath> using namespace std; struct node { double x,y,c,k,g; int id; }; int n; bool cmp(node a,node b) { if(a.x!=b.x) return a.x<b.x; else return a.y<b.y; } node d[110]; double xx[210]; int bh(int i,double mx) { if(d[i].x<=mx&&d[i].x+d[i].c>=mx) return 1; else return 0; } int judge(int i,double mx) { if(!bh(i,mx))return 0; for(int kk=0;kk<n;kk++) if(bh(kk,mx)&&d[kk].y<d[i].y&&d[kk].g>=d[i].g) return 0;//这里面的=不要掉了 return 1; } int main() { int case1=0; while(scanf("%d",&n)!=EOF&&n){ memset(d,0,sizeof(d)); memset(xx,0,sizeof(xx)); for(int i=0;i<n;i++) { scanf("%lf %lf %lf %lf %lf",&d[i].x,&d[i].y,&d[i].c,&d[i].k,&d[i].g); xx[i*2]=d[i].x;xx[i*2+1]=d[i].x+d[i].c; d[i].id=i+1; } sort(d,d+n,cmp); sort(xx,xx+n*2); int m=unique(xx,xx+n*2)-xx; if(case1) printf("\n"); printf("For map #%d, the visible buildings are numbered as follows:\n",++case1); printf("%d",d[0].id); for(int i=1;i<n;i++) { int vis=0; for(int j=0;j<m-1;j++) { if(judge(i,(xx[j]+xx[j+1])/2)){vis=1;break;} } if(vis) printf(" %d",d[i].id); } printf("\n"); } return 0; }