prithivMLmods/Coder-Stat

1 2<script type="text/x-mathjax-config">3  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});4</script>5<script type='text/javascript' src='http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML'></script>6</script>7 8 9<h2>Problem D10Wall Clocks</h2>11 12<p>13You are the manager of a chocolate sales team. Your team customarily takes tea breaks every two hours, during which varieties of new chocolate products of your company are served. Everyone looks forward to the tea breaks so much that they frequently give a glance at a wall clock.14</p>15 16<p>17Recently, your team has moved to a new office. You have just arranged desks in the office. One team member asked you to hang a clock on the wall in front of her desk so that she will not be late for tea breaks. Naturally, everyone seconded her.18</p>19 20<p>21You decided to provide an enough number of clocks to be hung in the field of view of everyone. Your team members will be satisfied if they have at least one clock (regardless of the orientation of the clock) in their view, or, more precisely, within 45 degrees left and 45 degrees right (both ends inclusive) from the facing directions of their seats. In order to buy as few clocks as possible, you should write a program that calculates the minimum number of clocks needed to22meet everyone's demand.23</p>24 25<p>26The office room is rectangular aligned to north-south and east-west directions. As the walls are tall enough, you can hang clocks even above the door and can assume one's eyesight is not blocked by other members or furniture. You can also assume that each clock is a point (of size zero), and so you can hang a clock even on a corner of the room.27</p>28 29<p>30For example, assume that there are two members. If they are sitting facing each other at positions shown in Figure D.1(A), you need to provide two clocks as they see distinct sections of the wall. If their seats are arranged as shown in Figure D.1(B), their fields of view have a common point on the wall. Thus, you can meet their demands by hanging a single clock at the point. In Figure D.1(C), their fields of view have a common wall section. You can meet their demands with a single clock by hanging it anywhere in the section. Arrangements (A), (B), and (C) in Figure D.1 correspond to Sample Input 1, 2, and 3, respectively.31</p>32 33 34<h3>Input</h3>35 36<p>37The input consists of a single test case, formatted as follows.<br>38<br>39 40$n$ $w$ $d$<br>41$x_1$ $y_1$ $f_1$<br>42...<br>43$x_n$ $y_n$ $f_n$<br>44<br>45</p>46 47<center>48<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_ICPCAsia2015_WallClocks" width="680"><br>49<p>Figure D.1. Arrangements of seats and clocks. Gray area indicates field of view.</p>50</center>51 52<p>53All numbers in the test case are integers. The first line contains the number of team members $n$ $(1 \leq n \leq 1,000)$ and the size of the office room $w$ and $d$ $(2 \leq w, d \leq 100,000)$. The office room has its width $w$ east-west, and depth $d$ north-south. Each of the following $n$ lines indicates the position and the orientation of the seat of a team member. Each member has a seat at a distinct position $(x_i, y_i)$ facing the direction $f_i$, for $i = 1, ..., n$. Here $1 \leq x_i \leq w - 1, 1 \leq y_i \leq d - 1$, and $f_i$ is one of <span>N</span>, <span>E</span>, <span>W</span>, and <span>S</span>, meaning north, east, west, and south, respectively. The position $(x, y)$ means $x$ distant from the west wall and $y$ distant from the south wall.54</p>55 56 57<h3>Output</h3>58 59<p>60Print the minimum number of clocks needed.61</p>62 63 64<h3>Sample Input 1</h3>65 66<pre>2 10 6674 4 E686 4 W</pre>69 70<h3>Sample Output 1</h3>71 72<pre>2</pre>73 74 75 76<h3>Sample Input 2</h3>77 78<pre>2 10 6792 4 E806 4 W</pre>81 82<h3>Sample Output 2</h3>83 84<pre>1</pre>85 86 87 88<h3>Sample Input 3</h3>89 90<pre>2 10 6913 2 S926 4 W</pre>93 94<h3>Sample Output 3</h3>95 96<pre>1</pre>97 98 99 100 101<h3>Sample Input 4</h3>102 103<pre>6 10 61041 5 N1057 1 N1068 2 E1079 1 S1084 4 S1093 3 W</pre>110 111<h3>Sample Output 4</h3>112 113<pre>3</pre>114 115 116 117<h3>Sample Input 5</h3>118 119<pre>4 10 61204 3 W1212 4 N1224 4 W1233 3 S</pre>124 125<h3>Sample Output 5</h3>126 127<pre>2</pre>128 129 130 131 132<h3>Sample Input 6</h3>133 134<pre>4 100000 4000013525000 25000 S13620000 30000 S13775000 25000 S13880000 30000 S</pre>139 140<h3>Sample Output 6</h3>141 142<pre>1</pre>143