Shortcut(二维平面内点的连续性) - c++编程基础

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）

NNNENNWWWSSW

Sample Output（shortcut.out）

2 3 11 W

题目满足：

45%的数据n<=1000

100%的数据n<=250000

时限 2s

本题最重要的是注意到二维平面内点的连续性。。

因为接近最短且路径不相交，所以在网格·内点在一条直线上相邻

所以只要排个序就行。。。etc...







#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
using namespace std;  
#define For(i,n) for(int i=1;i<=n;i++)  
#define Rep(i,n) for(int i=0;i=0;i--)  
#define MEM(a) memset(a,0,sizeof(a))  
#define MEMI(a) memset(a,127,sizeof(a))  
#define MEMi(a) memset(a,128,sizeof(a))  
#define INF (2139062143)  
#define F (1000000009)  
#define MAXN (50000+10)  
#define MAXM (500000+10)  
typedef long long ll;  
int father[MAXN]={0},dis[MAXN]={0},n,m;  
int getfather(int x)  
{  
   if (father[x]==x) return x;  
   int q_father=father[x];  
   father[x]=getfather(father[x]);  
   dis[x]=(dis[x]^dis[q_father])&1;  
   return father[x];  
}  
void union2(int x,int y)  
{  
   int i=getfather(x),j=getfather(y);  
   if(i