题意大概是这样，如上图所示，粗线描述的是一个人从家到学校的网格图上的路径，现在他想找一条捷径，shortcut，即两端都在路径顶点上且不与任何一条路径相交，问最短的捷径为多长。如果有重复，则要求起点编号尽量小，如果再重复，则终点编号尽量大。
这题要分别统计水平捷径和垂直捷径。以统计水平捷径为例：
1、对所有点的y坐标进行离散化（不离散化统计的时候hash也行。。）
2、对所有点坐标以x坐标降序排列
3、对点进行扫描，判断当前点的y值是否在hash表内（即判断该点右侧是否有路径节点），如果存在的话用hash表中记录的前一个x值与当前点的x值作差，然后与当前最小值比较，如果小于当前最小值，则更新节点；然后更新hash表中的值为当前点的x值
剩下的就是细节的处理了- -
贴代码（nlogn跑了1s多，有点不爽）
1 # include <cstdio>
2 # include <algorithm>
3 # include <cstring>
4 using namespace std;
5 struct node
6 {
7 bool r,u;
8 int x,y;
9 int mapx,mapy;
10 int pos;
11 }data[250005];
12 bool cmpx(const node &a,const node &b)
13 {
14 return a.x>b.x;
15 }
16 bool cmpy(const node &a,const node &b)
17 {
18 return a.y>b.y;
19 }
20 char str[250005];
21 int id[250005];
22 int len;
23 int main()
24 {
25 scanf("%d",&len);
26 scanf("%s",str);
27 len++;
28 int x=0,y=0;
29 for(int i=0;i<len;i++)
30 data[i].u=data[i].r=1;
31 for(int i=0;i<len-1;i++)
32 {
33 data[i].x=x;
34 data[i].y=y;
35 data[i].pos=i;
36
37 switch(str[i])
38 {
39 case 'N':
40 y++;
41 data[i].u=0;
42 break;
43 case 'E':
44 data[i].r=0;
45 x++;
46 break;
47 case 'S':
48 data[i+1].u=0;
49 y--;
50 break;
51 case 'W':
52 data[i+1].r=0;
53 x--;
54 break;
55 };
56 }
57 int res=0xfffffff,s,e;
58 char dir;
59 data[len-1].x=x;
60 data[len-1].y=y;
61 data[len-1].pos=len-1;
62 sort(data,data+len,cmpx);
63 data[len-1].mapx=0;
64 for(int i=len-2;i>=0;i--)
65 if(data[i].x==data[i+1].x)
66 data[i].mapx=data[i+1].mapx;
67 else
68 data[i].mapx=data[i+1].mapx+1;
69 sort(data,data+len,cmpy);
70 data[len-1].mapy=0;
71 for(int i=len-2;i>=0;i--)
72 if(data[i].y==data[i+1].y)
73 data[i].mapy=data[i+1].mapy;
74 else
75 data[i].mapy=data[i+1].mapy+1;
76 memset(id,-1,sizeof(id));
77 for(int i=0;i<len;i++)
78 {
79 if(id[data[i].mapx]!=-1&&data[i].u)
80 if(data[id[data[i].mapx]].y-data[i].y<res||data[id[data[i].mapx]].y-data[i].y==res&&min(data[id[data[i].mapx]].pos,data[i].pos)<s||data[id[data[i].mapx]].y-data[i].y==res&&min(data[id[data[i].mapx]].pos,data[i].pos)==s&&max(data[id[data[i].mapx]].pos,data[i].pos)>e)
81 {
82 res=data[id[data[i].mapx]].y-data[i].y,s=min(data[id[data[i].mapx]].pos,data[i].pos),e=max(data[id[data[i].mapx]].pos,data[i].pos);
83 if(data[i].pos<data[id[data[i].mapx]].pos) dir='N';
84 else dir='S';
85 }
86 id[data[i].mapx]=i;
87 }
88 sort(data,data+len,cmpx);
89 memset(id,-1,sizeof(id));
90 for(int i=0;i<len;i++)
91 {
92 if(id[data[i].mapy]!=-1&&data[i].r)
93 if(data[id[data[i].mapy]].x-data[i].x<res||data[id[data[i].mapy]].x-data[i].x==res&&min(data[id[data[i].mapy]].pos,data[i].pos)<s||data[id[data[i].mapy]].x-data[i].x==res&&min(data[id[data[i].mapy]].pos,data[i].pos)==s&&max(data[id[data[i].mapy]].pos,data[i].pos)>e)
94 {
95 res=data[id[data[i].mapy]].x-data[i].x,s=min(data[id[data[i].mapy]].pos,data[i].pos),e=max(data[id[data[i].mapy]].pos,data[i].pos);
96 if(data[i].pos<data[id[data[i].mapy]].pos)
97 dir='E';
98 else
99 dir='W';
100 }
101 id[data[i].mapy]=i;
102 }
103 printf("%d %d %d %c\n",res,s,e,dir);
104 return 0;
105 }
106