[SGU522] 油井（Oil Wells）

题目描述

BerOil 公司拥有若干口油井。Tapochkin 希望购买一块包含所有油井的土地，并使用一台自动筑篱机沿土地边界修建围栏。

整个平面被南北方向和东西方向的道路划分成边长为 $1$ 的无限方格。油井位于格点上，可以视为没有大小的点。筑篱机每次只能沿道路向北、东、南、西移动 $1$ 千米。

筑篱机发生了故障。启动前，驾驶员必须把四个方向分成两组，每组恰好包含两个互相垂直的方向。例如，可以把“北、东”分为第一组，把“南、西”分为第二组。

机器的整段行程必须满足：

1. 开始的一段时间内，只能使用第一组中的两个方向；
2. 在某一时刻切换一次；
3. 此后只能使用第二组中的两个方向。

驾驶员可以自行选择四个方向的分组以及切换时刻。

已知筑篱机初始位置以及所有油井的位置。你需要找到面积最小的一块土地，使得所有油井都位于土地内部或边界上，并给出筑篱机沿该土地边界行驶的一条合法路线。

土地边界必须是一条闭合、非退化，并且既不自交也不自触的折线。

输入格式

第一行包含三个整数 $n,x_0,y_0$，其中 $n$ 为油井数量，$(x_0,y_0)$ 为筑篱机初始位置。

接下来 $n$ 行，每行两个整数 $x_i,y_i$，表示一口油井的位置。

保证任意两口油井的坐标不同。

输出格式

如果不存在合法方案，输出一行：

-1

否则：

• 第一行输出最小土地面积，单位为平方千米；
• 第二行输出一个只由字符 W、N、E、S 组成的字符串，依次表示机器每次向西、北、东、南移动 $1$ 千米。

可以顺时针或逆时针沿边界行驶。如果最优方案不唯一，输出任意一种即可。

数据范围

$1\le n\le400$，$-400\le x_0,y_0\le400$，$-400\le x_i,y_i\le400$。

样例 1

样例输入

3 4 2
5 6
7 2
9 4

样例输出

13
NENNNEEEESSWWSSWWW

样例 2

样例输入

2 1 -2
-1 2
1 -2

样例输出

5
NWNNNWSSSSEE

样例 3

样例输入

1 1 2
1 2

样例输出

1
ESWN