UVA 221 - Urban Elevations(城市正视图) By SuCicada

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
/*
两个方块的比较:
比 x, y, 高
先比 x, 小的 小
    x 相同 比


存方块 vector<Build> 
存x   map<int, vector<int> >  x->List[index]



插入新的build
比x, 若已有 
     若无则插入, 
            =>  得到前一个: 得到前一个中组中的最后一个(即宽度最大的)  比其是否 > this
                                                                若 < : 无视
                                                                若 > : 比y
                得到后一个: 比 this.宽度+x 是否大于 后一个的x
    
    
- 
- 得到显示的方块
- 排序

*/

class Build{
public:
    double x,y,w,d,h;
    int index;
    bool operator <(const Build &bb){
        if(x < bb.x) return true;
        else if(x==bb.x) return y < bb.y;
        else return false;
    }
};
vector<Build> buildList;

vector<int> xList;

int isShow(int bi, int xx){
    if(buildList[bi].x < xx && buildList[bi].x+buildList[bi].w > xx){
        for(int i=0;i<buildList.size();i++){
            if(i!=bi && 
                buildList[i].x < xx && buildList[i].x+buildList[i].w > xx && 
                buildList[i].y < buildList[bi].y && 
                buildList[i].h >= buildList[bi].h){
                return 0;
            }
        }
        return 1;
    }
    /* 不在范围 */
    return -1;
}

int main(){
    int T;
    int N=1;
    while(cin>>T && T){
        buildList.clear();
        xList.clear();
        for(int i=1;i<=T;i++){
            double x,y,w,d,h;
            cin>>x>>y>>w>>d>>h;
            Build b;
            b.x = x;
            b.y = y;
            b.w = w;
            b.d = d;
            b.h = h;
            b.index = i;
            buildList.push_back(b);
            xList.push_back(x);
            xList.push_back(x+w);
        }

        sort(buildList.begin(), buildList.end());
        sort(xList.begin(), xList.end());

        vector<int>::iterator vi = unique(xList.begin(), xList.end());
        xList.erase(vi,xList.end());

        if(N>1){
            cout<<endl;
        }
        cout<<"For map #"<< N++ <<", the visible buildings are numbered as follows:"<<endl;
        int one = 0;
        for(int i=0;i<buildList.size();i++){
            int show = 0;
            for(int j=0;j<xList.size()-1;j++){
                int xi = (xList[j] + xList[j+1]) / 2;
                show = isShow(i,xi);
                if(show==1){
                    break;
                }
            }
            if(show==1){
                if(one){
                    cout<<" ";
                }
                cout<<buildList[i].index;
                one = 1;
            }
        }
        cout<<endl;

    }
    return 0;
}

// AC at 2020/09/10