对于每个祭坛，算出每条线段阻碍它的角度区间，然后排序求并看看是否有空位即可，时间复杂度$O(n^2log n)$。
这题在Main上官方时限是0.2S，因此需要几个常数优化：
$1.$为了避免用atan2(y,x)算角度，改成算斜率，所以需要分$4$个方向讨论。
$2.$对区间排序时，不要直接对结构体排序，而是对其指针排序。
$3.$在计算某个祭坛时，除了它本身需要特别计算之外，其它祭坛可以直接看成没有缺口的矩形，可以减少$n$个事件。
$4.$在计算的过程中，不断收缩左右边界，当左右边界重合时即可直接判定为不可能。
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1005,BUF=50000;
const double eps=1e-9,inf=1e9;
int n,m,cnt,i,X,k,ce,flag;char dir[N],Buf[BUF],*buf=Buf;double L,R;
inline void read(int&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;}
inline void read(char&a){while(*buf<'A')buf++;a=*buf++;}
struct P{int x,y;P(){}P(int _x,int _y){x=_x,y=_y;}}a[N];
struct seg{
P x,y;
seg(){}
seg(P _x,P _y){
x=_x,y=_y;
if(x.x>y.x||x.y>y.y)swap(x,y);
}
}b[N*5],c[N*4],f[N];
struct E{
double l,r;
void set(double _l,double _r){
l=_l,r=_r;
if(l<L+eps)L=max(L,r);
if(r>R-eps)R=min(R,l);
if(L+eps>R)k=1;
}
}e[N*4],*q[N*4];
inline bool cmp(E*x,E*y){return x->l<y->l;}
inline bool cal(int x,int y,double&t){
if(x<=0)return 0;
t=1.0*y/x;
return 1;
}
inline double fix(double x){return x>0?inf:-inf;}
void initS(int x,int y){
cal(-f[X].x.y+y,f[X].x.x-x,L);
cal(-f[X].y.y+y,f[X].y.x-x,R);
if(L>R)swap(L,R);
for(int i=1;i<=m;i++)if((i+4)/5==X){
seg&j=b[i];double l,r;
if(!cal(-j.x.y+y,j.x.x-x,l))continue;
if(!cal(-j.y.y+y,j.y.x-x,r))r=fix(l);
if(l>r)swap(l,r);
if(r<L-eps||l>R+eps)continue;
e[ce++].set(l,r);
}
for(int i=1;i<=cnt&&!k;i++)if((i+3)/4!=X){
seg&j=c[i];double l,r;
if(!cal(-j.x.y+y,j.x.x-x,l))continue;
if(!cal(-j.y.y+y,j.y.x-x,r))r=fix(l);
if(l>r)swap(l,r);
if(r<L-eps||l>R+eps)continue;
e[ce++].set(l,r);
}
}
void initN(int x,int y){
cal(f[X].y.y-y,f[X].y.x-x,L);
cal(f[X].x.y-y,f[X].x.x-x,R);
if(L>R)swap(L,R);
for(int i=1;i<=m;i++)if((i+4)/5==X){
seg&j=b[i];double l,r;
if(!cal(j.y.y-y,j.y.x-x,r))continue;
if(!cal(j.x.y-y,j.x.x-x,l))l=fix(r);
if(l>r)swap(l,r);
if(r<L-eps||l>R+eps)continue;
e[ce++].set(l,r);
}
for(int i=1;i<=cnt&&!k;i++)if((i+3)/4!=X){
seg&j=c[i];double l,r;
if(!cal(j.y.y-y,j.y.x-x,r))continue;
if(!cal(j.x.y-y,j.x.x-x,l))l=fix(r);
if(l>r)swap(l,r);
if(r<L-eps||l>R+eps)continue;
e[ce++].set(l,r);
}
}
void initW(int x,int y){
cal(-f[X].x.x+x,f[X].x.y-y,L);
cal(-f[X].y.x+x,f[X].y.y-y,R);
if(L>R)swap(L,R);
for(int i=1;i<=m;i++)if((i+4)/5==X){
seg&j=b[i];double l,r;
if(!cal(-j.x.x+x,j.x.y-y,l))continue;
if(!cal(-j.y.x+x,j.y.y-y,r))r=fix(l);
if(l>r)swap(l,r);
if(r<L-eps||l>R+eps)continue;
e[ce++].set(l,r);
}
for(int i=1;i<=cnt&&!k;i++)if((i+3)/4!=X){
seg&j=c[i];double l,r;
if(!cal(-j.x.x+x,j.x.y-y,l))continue;
if(!cal(-j.y.x+x,j.y.y-y,r))r=fix(l);
if(l>r)swap(l,r);
if(r<L-eps||l>R+eps)continue;
e[ce++].set(l,r);
}
}
void initE(int x,int y){
cal(f[X].y.x-x,f[X].y.y-y,L);
cal(f[X].x.x-x,f[X].x.y-y,R);
if(L>R)swap(L,R);
for(int i=1;i<=m;i++)if((i+4)/5==X){
seg&j=b[i];double l,r;
if(!cal(j.y.x-x,j.y.y-y,r))continue;
if(!cal(j.x.x-x,j.x.y-y,l))l=fix(r);
if(l>r)swap(l,r);
if(r<L-eps||l>R+eps)continue;
e[ce++].set(l,r);
}
for(int i=1;i<=cnt&&!k;i++)if((i+3)/4!=X){
seg&j=c[i];double l,r;
if(!cal(j.y.x-x,j.y.y-y,r))continue;
if(!cal(j.x.x-x,j.x.y-y,l))l=fix(r);
if(l>r)swap(l,r);
if(r<L-eps||l>R+eps)continue;
e[ce++].set(l,r);
}
}
bool check(){
if(k)return 0;
for(int i=0;i<ce;i++)q[i]=e+i;
sort(q,q+ce,cmp);
for(int i=0;i<ce;i++){
if(q[i]->l>L+eps)return 1;
if(L<q[i]->r)L=q[i]->r;
}
return 0;
}
int main(){
fread(Buf,1,BUF,stdin);read(n);
for(i=1;i<=n;i++){
int x1,y1,x2,y2,o;char d;
read(x1),read(y1),read(x2),read(y2),read(d);
x1<<=2,y1<<=2,x2<<=2,y2<<=2;
if(x1>x2)swap(x1,x2);
if(y1>y2)swap(y1,y2);
a[i]=P((x1+x2)/2,(y1+y2)/2);
dir[i]=d;
if(d!='S')b[++m]=seg(P(x1,y1),P(x2,y1));
else{
o=(x1+x2)/2;
b[++m]=seg(P(x1,y1),P((x1+o)/2,y1));
b[++m]=seg(P(x2,y1),P((x2+o)/2,y1));
f[i]=seg(P((x1+o)/2,y1),P((x2+o)/2,y1));
}
if(d!='N')b[++m]=seg(P(x1,y2),P(x2,y2));
else{
o=(x1+x2)/2;
b[++m]=seg(P(x1,y2),P((x1+o)/2,y2));
b[++m]=seg(P(x2,y2),P((x2+o)/2,y2));
f[i]=seg(P((x1+o)/2,y2),P((x2+o)/2,y2));
}
if(d!='W')b[++m]=seg(P(x1,y1),P(x1,y2));
else{
o=(y1+y2)/2;
b[++m]=seg(P(x1,y1),P(x1,(y1+o)/2));
b[++m]=seg(P(x1,y2),P(x1,(y2+o)/2));
f[i]=seg(P(x1,(y1+o)/2),P(x1,(y2+o)/2));
}
if(d!='E')b[++m]=seg(P(x2,y1),P(x2,y2));
else{
o=(y1+y2)/2;
b[++m]=seg(P(x2,y1),P(x2,(y1+o)/2));
b[++m]=seg(P(x2,y2),P(x2,(y2+o)/2));
f[i]=seg(P(x2,(y1+o)/2),P(x2,(y2+o)/2));
}
c[++cnt]=seg(P(x1,y1),P(x2,y1));
c[++cnt]=seg(P(x1,y2),P(x2,y2));
c[++cnt]=seg(P(x1,y1),P(x1,y2));
c[++cnt]=seg(P(x2,y1),P(x2,y2));
}
for(X=1;X<=n;X++){
ce=k=0;
if(dir[X]=='S')initS(a[X].x,a[X].y);
if(dir[X]=='N')initN(a[X].x,a[X].y);
if(dir[X]=='W')initW(a[X].x,a[X].y);
if(dir[X]=='E')initE(a[X].x,a[X].y);
if(check())flag=1,printf("%d
",X);
}
if(!flag)puts("BRAK");
return 0;
}