# POI1999 祭坛问题## 题目背景在中国民间人们相信鬼只能沿直线移动。在修建寺庙时那是非常重要的。## 题目描述寺庙要修建在四边分别平行于南北西东的矩形位置之上。两个矩形不能有公共交点。入口位于四堵墙中一堵的中间门的宽度等于墙长度的一半。祭坛出现在寺庙的中间矩形的对角线在那里相交。鬼魂在这个点出现那么寺庙被亵渎当且仅当存在从祭坛射出的一束光线通过入口到外面而且不与其他寺庙位于建筑区域平行的

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Temple {
    int x1, y1, x2, y2;
    char entrance;
};

bool intersect(const Temple& t1, const Temple& t2) {
    if (t1.x1 >= t2.x2 || t1.x2 <= t2.x1 || t1.y1 >= t2.y2 || t1.y2 <= t2.y1) {
        return false;
    }
    return true;
}

bool isDesecrated(const Temple& temple, const vector<Temple>& temples) {
    int x1 = temple.x1;
    int x2 = temple.x2;
    int y1 = temple.y1;
    int y2 = temple.y2;

    // 判断是否与其他寺庙相交
    for (const auto& t : temples) {
        if (intersect(temple, t)) {
            return false;
        }
    }

    // 判断是否能够从祭坛射出光线
    if (temple.entrance == 'E') {
        for (const auto& t : temples) {
            if (t.x1 < x1 && t.y1 <= y1 && t.y2 >= y2) {
                return false;
            }
        }
    } else if (temple.entrance == 'W') {
        for (const auto& t : temples) {
            if (t.x2 > x2 && t.y1 <= y1 && t.y2 >= y2) {
                return false;
            }
        }
    } else if (temple.entrance == 'S') {
        for (const auto& t : temples) {
            if (t.y1 < y1 && t.x1 <= x1 && t.x2 >= x2) {
                return false;
            }
        }
    } else if (temple.entrance == 'N') {
        for (const auto& t : temples) {
            if (t.y2 > y2 && t.x1 <= x1 && t.x2 >= x2) {
                return false;
            }
        }
    }

    return true;
}

int main() {
    int n;
    cin >> n;

    vector<Temple> temples(n);
    for (int i = 0; i < n; ++i) {
        cin >> temples[i].x1 >> temples[i].y1 >> temples[i].x2 >> temples[i].y2 >> temples[i].entrance;
    }

    vector<int> desecratedTemples;
    for (int i = 0; i < n; ++i) {
        if (isDesecrated(temples[i], temples)) {
            desecratedTemples.push_back(i + 1);
        }
    }

    if (desecratedTemples.empty()) {
        cout << "BRAK" << endl;
    } else {
        for (const auto& t : desecratedTemples) {
            cout << t << endl;
        }
    }

    return 0;
}
``