Shortcut(二维平面内点的连续性)

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<cstdio>  
#include<cstdlib>  
#include<cstring>  
#include<iostream>  
#include<algorithm>  
#include<functional>  
#include<cmath>  
#include<cctype>  
#include<cassert>  
#include<climits>  
using namespace std;  
#define For(i,n) for(int i=1;i<=n;i++)  
#define Rep(i,n) for(int i=0;i<n;i++)  
#define Fork(i,k,n) for(int i=k;i<=n;i++)  
#define ForD(i,n) for(int i=n;i;i--)  
#define Forp(x) for(int p=pre[x];p;p=next[p])  
#define RepD(i,n) for(int i=n;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<j) swap(i,j);  
   father[i]=j;  
   dis[i]=((dis[x]^dis[y])&1)^1;     
}  
int color[MAXN]={0};  
int main()  
{  
   freopen("relation.in","r",stdin);  
   freopen("relation.out","w",stdout);  
   scanf("%d%d",&n,&m);  
   For(i,n) father[i]=i;  
   For(i,m)  
   {  
      int x,y;  
      scanf("%d%d",&x,&y);  
      if (getfather(x)^getfather(y)) union2(x,y);  
      else  
      {  
         if (dis[x]==dis[y])  
         {  
            puts("IMPOSSIBLE");  
            return 0;  
         }  
      }  
   }     
   For(i,n) getfather(i); //不能用father[x]=getfather(father[x]);   
   /**/  
// For(i,10) cout<<father[i]<<' '<<dis[i]<<endl;  
   /**/  
   int tot2=0;  
   For(i,n)   
   {  
      if (father[i]==i) color[i]=2;  
      else color[i]=color[father[i]]^dis[i];  
      if (color[i]==2) tot2++;      
   }  
   int tot3=n-tot2;  
     
   bool b=0;  
   For(i,n) if (color[i]==2){if (b) printf(" %d",i);else printf("%d",i),b=1;}  
   puts("");  
   b=0;  
   For(i,n) if (color[i]==3){if (b) printf(" %d",i);else printf("%d",i),b=1;}  
   puts("");  
     
        
// while(1);  
   return 0;  
}

补充：软件开发 , C++ ,