6705: 抓拍

<div class=panel_title align=left>Problem Description</div> <div class=panel_content>学校里有 $n$ 名同学，初始时第 $i$ 位同学从 $(x_i, y_i)$ 出发，以每秒 $1$ 米的速度散步。<br><br>同学们散步的方向有东南西北四种可能。假设有一位同学正在位于 $(0, 0)$，则下一秒︰<br><br>- 如果向东走，到达 $(1, 0)$<br>- 如果向西走，到达 $(-1, 0)$<br>- 如果向南走，到达 $(0, -1)$<br>- 如果向北走，到达 $(0, 1)$<br><br>假设散步过程会进行无限长的时间，同学们散步的方向不会改变，并且忽略碰撞的情况（允许某个时刻多人在同一个点，互不影响）。<br><br>现在你可以选择某个**非负整数**秒时刻抓拍照片。<br><br>一张照片可以用长方形 $((e, n), (w, s))$ 表示，东北角为 $(e, n)$，西南角为 $(w, s)$。<br><br>只有抓拍的照片包含了所有同学时，我们才称这张照片是完美的。<br><br>请选择某个时刻抓拍一张完美的照片，使得照片的周长最小。</div><div class=panel_bottom>&nbsp;</div><br>

第一行一个整数 $n\ (1 \leq n \leq 2 \times 10^5)$，代表人数。<br><br>接下来 $n$ 行，第 $i$ 行包含两个整数 $x_i, y_i\ (-10^9 \leq x_i, y_i \leq 10^9)$ 和一个字符 $d_i$ ，由空格分隔，描述第 $i$ 位同学。<br><br>$d_i$ 是 &#039;E&#039;, &#039;W&#039;, &#039;S&#039;, &#039;N&#039; 之一，分别代表第 $i$ 位同学散步的方向是东、西、南、北。

输出一行一个整数，代表最短的完美照片的周长。