벽시계

시간 제한1초메모리 제한256 MB

요약

90도 시야에 들어오는 벽 구간을 자리마다 구한 뒤 모든 자리가 시계 하나 이상을 보도록 가장 적은 시계 위치 개수를 구합니다.

난이도: 보통10점 중 6점
유형: 그리디, 구간, 기하
정답자: 아직 제출이 없습니다

문제

당신은 초콜릿 영업팀의 팀장이다. 팀은 두 시간마다 티타임을 갖고, 그때마다 회사가 새로 내놓은 초콜릿을 맛본다. 모두가 티타임을 기다리기 때문에 벽시계를 자주 쳐다본다.

얼마 전 팀이 새 사무실로 옮겼고, 당신은 방금 책상 배치를 끝냈다. 한 팀원이 티타임에 늦지 않도록 자기 책상 앞 벽에 시계를 걸어 달라고 부탁했고, 다른 팀원도 모두 그 말에 찬성했다.

그래서 모든 팀원의 시야에 시계가 들어오도록 시계를 충분히 걸기로 했다. 팀원은 자기 좌석이 바라보는 방향에서 왼쪽으로 45도, 오른쪽으로 45도까지의 범위(양 끝 포함) 안에 시계가 하나라도 있으면 만족한다. 시계가 어느 쪽으로 걸려 있는지는 상관없다. 시계를 되도록 적게 사려고 한다. 모두의 요구를 만족시키는 데 필요한 시계의 최소 개수를 구하라.

사무실은 직사각형이고 각 변은 동서 방향과 남북 방향에 나란하다. 벽이 충분히 높아서 문 위에도 시계를 걸 수 있고, 다른 팀원이나 가구가 시야를 가리는 일도 없다. 시계는 크기가 0인 점이므로 방의 모서리에도 걸 수 있다.

좌석과 시계의 배치

그림 1. 좌석과 시계의 배치. 회색 영역이 시야다.

예를 들어 팀원이 두 명이라고 하자. 그림 1(A)처럼 서로 마주 보고 앉아 있으면 두 사람이 보는 벽의 구간이 겹치지 않으므로 시계가 두 개 필요하다. 그림 1(B)의 배치에서는 두 사람의 시야가 벽 위의 한 점에서 만나므로 그 점에 시계를 하나 걸면 된다. 그림 1(C)에서는 두 시야가 벽의 한 구간을 공유하므로 그 구간 어디에 걸든 시계 하나로 충분하다. 그림 1의 배치 (A), (B), (C)는 각각 첫 번째, 두 번째, 세 번째 예제에 해당한다.

입력

입력은 테스트 케이스 하나로 이루어지며, 형식은 다음과 같다.

n w d
x1 y1 f1
...
xn yn fn

입력의 모든 값은 정수다. 첫 줄에 팀원 수 $n$ ( $1 \le n \le 1000$ )과 사무실의 크기 $w$ , $d$ ( $2 \le w, d \le 100000$ )가 주어진다. 사무실의 동서 방향 너비는 $w$ , 남북 방향 깊이는 $d$ 다. 이어지는 $n$ 개의 줄에는 팀원 좌석의 위치와 방향이 주어진다. $i$ 번째 팀원의 좌석은 위치 $(x_i, y_i)$ 에 있고 방향 $f_i$ 를 바라본다. $1 \le x_i \le w - 1$ , $1 \le y_i \le d - 1$ 이고, $f_i$ 는 N, E, W, S 중 하나로 각각 북쪽, 동쪽, 서쪽, 남쪽을 뜻한다. 위치 $(x, y)$ 는 서쪽 벽에서 $x$ 만큼, 남쪽 벽에서 $y$ 만큼 떨어진 지점이다. 좌석의 위치는 서로 다르다.

출력

필요한 시계의 최소 개수를 출력한다.

예제6

예제 1
입력
```
2 10 6
4 4 E
6 4 W
```
예상 출력
```
2
```
예제 2
입력
```
2 10 6
2 4 E
6 4 W
```
예상 출력
```
1
```
예제 3
입력
```
2 10 6
3 2 S
6 4 W
```
예상 출력
```
1
```

예제 4

입력

예상 출력

예제 5
입력
```
4 10 6
4 3 W
2 4 N
4 4 W
3 3 S
```
예상 출력
```
2
```

예제 6

입력

4 100000 40000
25000 25000 S
20000 30000 S
75000 25000 S
80000 30000 S

예상 출력