[UVA] 221 - Urban Elevations

題意:
給你一個城市的俯視圖，
輸入每一棟建築物的
。x 座標
。y 座標
。寬
。長
。高
每一個資訊都是實數，(不是整數)
建築物編號為輸入順序，
例如第一個輸入的編號為1
問正視圖中可見的建築物有哪些，
輸出建築物編號，
以建築物的 x 座標由小到大輸出，
注意!若 x 座標相同以建築物 y 座標由小到大輸出!
例如:
輸入
3//三個建築物
0 0 10 1 50
0 1 11 1 20
0 2 10 1 100

建築物1 2 3都可看到，
但要依照 x 座標案 y 座標輸出，
所以輸出1 2 3。


方法:
離散化
可以列舉每一個x座標，然後看該 x 座標有哪些建築物可見，
但是問題在於，x 座標有無限個，不可能全部列舉，
所以用離散化的方式，將無限變有限。
作法是將每一個建築物的頭和尾的 x 座標紀錄起來排序後做unique，
然後去列舉這些 x 座標就好，
判斷在 x 座標為 i 時該建築物可不可見，
先判斷該建築物是否有覆蓋到 i (頭<=i<=尾)，
然後再判斷該建築物前面是否有比他高的，
也就是 y 座標比該建築物小的也覆蓋到 i ，是否有比他高!

注意!每一筆測資之間需空一行，最後一筆測資後面不需要空行。



/* 20150812
 * hanting
 * UVa 221 - Urban Elevations
 * C++
 */
#include <iostream>
#include <vector>
#include <algorithm>//sort,unique
using namespace std;
struct Building
{
    int id;
    double x,y,width,depth,height;
    friend istream& operator>>(istream& in,Building &b)
    {
        in>>b.x>>b.y>>b.width>>b.depth>>b.height;
        return in;
    }
    bool operator<(const Building &B)const
    {
        return (x<B.x) or (x==B.x and y<B.y);
    }
    bool cover(double t)
    {
        return t>=x and t<=x+width;
    }
    bool visible(double x,Building *b,int n)
    {
        for(int i=0;i<n;i++)
        {
            if(b[i].cover(x) and b[i].y<y and b[i].height>=height) return false;
        }
        return true;
    }
};
int main()
{
    int buildingN;
    int Case=1;
    int blank=0;
    while(cin>>buildingN and buildingN)
    {
        if(blank++) cout<<endl;
        Building building[buildingN];
        double xCoor[buildingN*2];
        for(int i=0;i<buildingN;i++)
        {
            cin>>building[i];
            building[i].id=i+1;//編號從1開始
            xCoor[i*2]=building[i].x;
            xCoor[i*2+1]=building[i].x+building[i].width;
        }
        sort(building,building+buildingN);
        sort(xCoor,xCoor+buildingN*2);
        int m=unique(xCoor,xCoor+buildingN*2)-xCoor;
        vector<int> ans;
        ans.push_back(0);

        for(int i=1;i<buildingN;i++)
        {
            for(int j=0;j<m-1;j++)
            {
                double x=(xCoor[j]+xCoor[j+1])/2;
                if(building[i].cover(x) and building[i].visible(x,building,buildingN))
                {
                    ans.push_back(i);
                    break;
                }
            }
        }

        cout<<"For map #"<<Case++<<", the visible buildings are numbered as follows:"<<endl;

        for(int i=0;i<ans.size()-1;i++)
        {
            cout<<building[ans[i]].id<<" ";
        }
        cout<<building[ans.back()].id<<endl;
    }
    return 0;
}