# Poj Solution 1763

```http://poj.org/problem?id=1763

#include<iostream>
#include"memory.h"
#include"algorithm"
using namespace std;
long x[260000],y[260000];
long ordx[260000],ordy[260000];
inline long abs(long a)
{return a>0?a:-a;}

int cmpx(long a,long b)
{return x[a]<x[b]||(x[a]==x[b]&&y[a]<y[b]);}
int cmpy(long a,long b)
{return y[a]<y[b]||(y[a]==y[b]&&x[a]<x[b]);}

int main()
{char c;long xn,yn,n,i,bb,eb,lb,b,e,l;
cin>>n;
xn=0;yn=0;ordx[0]=0;ordy[0]=0;x[0]=0;y[0]=0;

for(i=1;i<=n;i++)
{cin>>c;
switch(c)
{case'N':yn--;break;
case'S':yn++;break;
case'W':xn--;break;
case'E':xn++;break;
default:break;
}
x[i]=xn;y[i]=yn;ordx[i]=i;ordy[i]=i;
}

sort(&ordx[0],&ordx[n+1],cmpx);
sort(&ordy[0],&ordy[n+1],cmpy);
lb=99999999;

for(i=1;i<=n;i++)
if(x[ordx[i]]==x[ordx[i-1]])
{b=ordx[i]<ordx[i-1]?ordx[i]:ordx[i-1];
e=ordx[i]>ordx[i-1]?ordx[i]:ordx[i-1];
l=y[ordx[i]]-y[ordx[i-1]];
if((e-b)!=l)
{if(l<lb){lb=l;bb=b;eb=e;}
else if(l==lb){if(b<bb){bb=b;eb=e;}
else if(b==bb){if(e>eb)eb=e;}
}
}
}
for(i=1;i<=n;i++)
if(y[ordy[i]]==y[ordy[i-1]])
{b=ordy[i]<ordy[i-1]?ordy[i]:ordy[i-1];
e=ordy[i]>ordy[i-1]?ordy[i]:ordy[i-1];
l=x[ordy[i]]-x[ordy[i-1]];
if((e-b)!=l)
{if(l<lb){lb=l;bb=b;eb=e;}
else if(l==lb){if(b<bb){bb=b;eb=e;}
else if(b==bb){if(e>eb)eb=e;}
}
}
}

cout<<lb<<' '<<bb<<' '<<eb<<' ';
if(x[bb]==x[eb])
{if(y[eb]>y[bb])cout<<'S';
else cout<<'N';
}
if(y[bb]==y[eb])
{if(x[eb]>x[bb])cout<<'E';
else cout<<'W';
}
cout<<endl;
return 0;
}

```
This entry was posted in poj. Bookmark the permalink.