原题：
Description
Mirek有一条每天从他家去大学工作的最喜欢的路。这个路径由若干个部分组成，且每个部分是10米长的直线。每一个部分是直线连接（没有拐弯）上一个部分或垂直连接上一个部分。在走过每一个部分后，Mirek会休息下欣赏美丽的自然景色。在他走路的过程之中，他不会重复访问一个地点
昨天，Mirek在party中熬夜到很迟，并且今天他迟起床了。他意识到他会错过第一堂课除非他改变他平时走的路径。他计划找一条捷径（shortcut）但他希望捷径尽量的短。捷径必须是水平的或者是垂直的并且连接两个Mirek原先路径的休息的地点。
请帮助Mirek找到最短的捷径。
Task
写一个程序：
读入Mirek的路径，计算路径上面最短的捷径，输出结果。
Input
第一行包含一个整数n（3<=n<=250000）作为路径的部分的个数。第二行包含一组长度为n的序列，每个字母为N，E，S或W，
之间没有空格。每一个字母描述路径的一个部分。字母N，E，S或W表示Mirek向这些方向走了10米。你可以假设至少存在一个捷径。
Output
第一行也就是唯一的一行包括 l，b，e 3个整数和一个字母d，用空格隔开。整型变量l是最短的捷径（以长度10为单位）。整数b和e是休息点的编号，也就是捷径的起点和终点（Mirek的home的编号为0，大学的编号为n）。字母d是捷径的方向。如果有超过1条最短的捷径存在，你应该输出起点最小的，如果有多个捷径最短，起点相同的捷径，你应该输出终点编号最大的。
Sample Input（shortcut.in）
12
NNNENNWWWSSW
Sample Output（shortcut.out）
2 3 11 W
题目满足：
45%的数据n<=1000
100%的数据n<=250000
时限 2s
首先我们要理解shortcut的含义，他是一条在网格上的线段，且不与路径重合
然后我们想到了一个性质，即判断2点之间有无路径及判断点的指针与另一点的指针的差是否为1，若为1则为路径
然后就可以扫描线扫描点+统计答案。做2次即可
下面贴代码
#include<iostream> #include<cstdio> #include<algorithm> #define inf 0x3f3f3f3f using namespace std; int point[250005][2]; int sorted[250005]; int n,bestlen,bestbeg,bestend; bool cmp(int a,int b){return (point[a][0]<point[b][0])||((point[a][0]==point[b][0])&&(point[a][1]<point[b][1]));} bool cmp2(int a,int b){return (point[a][1]<point[b][1])||((point[a][1]==point[b][1])&&(point[a][0]<point[b][0]));} void sort1(int step) { for(int i=0;i<=n;i++) sorted[i]=i; sort(sorted,sorted+n+1,step==0?cmp:cmp2); } void solve(int step){ sort1(step); for(int i=1;i<=n;i++) { if(point[sorted[i-1]][step]==point[sorted[i]][step]) { int len=abs(point[sorted[i-1]][1-step]-point[sorted[i]][1-step]); int b=sorted[i-1]<sorted[i]?sorted[i-1]:sorted[i]; int e=b==sorted[i-1]?sorted[i]:sorted[i-1]; if(e-b!=1) if((len<bestlen)||(len==bestlen&&b<bestbeg)||((len==bestlen)&&(b==bestbeg)&&(e>bestend))) bestlen=len,bestbeg=b,bestend=e; } } } int main(){ freopen("shortcut.in","r",stdin); freopen("shortcut.out","w",stdout); bestbeg=n+1;bestend=-1;bestlen=inf; scanf("%d",&n); int x=0,y=0; char ch[250001]; scanf("%s",ch); point[0][0]=0;point[0][1]=0; for(int i=0;i<n;i++) { if(ch[i]=='N')++y; else if(ch[i]=='S')--y; else if(ch[i]=='W')--x; else ++x; point[i+1][0]=x;point[i+1][1]=y; } solve(0); solve(1); char ans; if(point[bestbeg][0]==point[bestend][0])ans=point[bestbeg][1]<point[bestend][1]?'N':'S'; else ans=point[bestbeg][0]<point[bestend][0]?'E':'W'; printf("%d %d %d %c ",bestlen,bestbeg,bestend,ans); return 0; fclose(stdin); fclose(stdout); }