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.

Leave a Reply

Your email address will not be published. Required fields are marked *