题意：
作图为n个建筑物的俯视图，右图为从南向北看的正视图，按从左往右的顺序输出可见建筑物的标号。
分析：
题中已经说了，要么x相同，要么x相差足够大，不会出现精度问题。
给这n个建筑物从左往右排序，每个建筑物的两个端点，排序去重以后可以得到m个相邻的小区间。枚举这些区间，判断建筑物是否可见。
离散化刚开始接触这个词，感觉十分高冷。现在来看倒是很形象，因为是浮点数，所以不可能枚举所有的横坐标，但可以分割成若干的小区间，这个进行判断。即：将无限变为有限。
再说一下unique函数，调用之前必须先排序，而且调用后并不是将重复元素删除，而是将其挪到后面去。
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 const int maxn = 100 + 5; 6 7 struct Buiding 8 { 9 int id; 10 double x, y, w, d, h; 11 bool operator < (const Buiding& rhs) const 12 { return x < rhs.x || (x == rhs.x && y < rhs.y); } 13 }b[maxn]; 14 15 int n; 16 double x[maxn * 2]; 17 18 bool isCover(int i, double posx) 19 { 20 return b[i].x <= posx && b[i].x + b[i].w >= posx; 21 } 22 23 bool isVisibal(int i, double posx) //第i个建筑物是否在该横坐标处可见 24 { 25 if(!isCover(i, posx)) return false; 26 for(int k = 0; k < n; ++k) 27 if(isCover(k, posx) && b[k].y < b[i].y && b[k].h >= b[i].h) 28 return false; 29 return true; 30 } 31 32 int main() 33 { 34 //freopen("in.txt", "r", stdin); 35 int kase = 0; 36 while(scanf("%d", &n) == 1 && n) 37 { 38 for(int i = 0; i < n; ++i) 39 { 40 scanf("%lf%lf%lf%lf%lf", &b[i].x, &b[i].y, &b[i].w, &b[i].d, &b[i].h); 41 b[i].id = i + 1; 42 x[i*2] = b[i].x, x[i*2+1] = b[i].x + b[i].w; 43 } 44 sort(b, b + n); 45 sort(x, x + n * 2); 46 int m = unique(x, x + n*2) - x; 47 48 if(kase) puts(""); 49 printf("For map #%d, the visible buildings are numbered as follows: %d", ++kase, b[0].id); 50 for(int i = 1; i < n; ++i) 51 { 52 bool flag = false; 53 for(int j = 0; j < m-1; ++j) 54 { 55 double posx = (x[j] + x[j+1]) / 2; 56 if(isVisibal(i, posx)) 57 { 58 flag = true; 59 break; 60 } 61 } 62 if(flag) printf(" %d", b[i].id); 63 } 64 printf(" "); 65 } 66 67 return 0; 68 }