Problem: Example

Input

2 10 6
4 4 E
6 4 W


Output

2

Solution (in CPP):

Solution:

#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>

auto& in = std::cin;
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;

int32_t H,W;
int32_t N;
std::pair<int32_t, int32_t> pos[3000];
int32_t solve(std::pair<int32_t, int32_t>* begin, std::pair<int32_t, int32_t>* end)
{
	int32_t limit = (H + W + H + W) * 3;
	int32_t count = 0;
	for (auto iter = begin; iter != end; iter++)
	{
		auto v = *iter;
		if (v.second < v.first) {
			v.second += H + W + H + W;
		}

		if (limit < v.first) {
			++count;
			limit = v.second;
		}
		else {
			limit = std::min(limit, v.second);
		}
	}
	++count;
	return count;
}

int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> N >> W>> H;

	for (size_t i = 0; i < N; i++)
	{
		int32_t x, y;
		char dir;
		in >> x >> y >> dir;

		auto get_lu = [&]() {
			//hで調整
			auto newx = x - (H - y);
			if (newx > 0) {
				return H + W + H + W - newx;
			}
			else {
				//wで調整
				auto newy = H - (y + x);
				return newy;
			}
		};
		auto get_ld = [&]() {
			auto newx = x - y;
			return H + newx;
		};
		auto get_ru = [&]() {
			auto newx = x + (H - y);
			return H + W + H + W - newx;
		};
		auto get_rd = [&]() {
			return H + x + y;
		};

		if (dir == 'N') {
			pos[i].first = get_ru();
			pos[i].second = get_lu();
		}
		else if (dir == 'S') {
			pos[i].first = get_ld();
			pos[i].second = get_rd();
		}
		else if (dir == 'W') {
			pos[i].first = get_lu();
			pos[i].second = get_ld();
		}
		else if (dir == 'E') {
			pos[i].first = get_rd();
			pos[i].second = get_ru();
		}
	}
	auto begin = pos;
	auto end = pos + N;
	std::sort(begin, end);
	int32_t res = (H + W + H + W) * 3;
	for (size_t i = 0; i < N; i++)
	{
		res = std::min(res, solve(begin, end));
		*end = *begin;
		end->first += H + W + H + W;
		end->second += H + W + H + W;
		++begin; ++end;
	}
	out << res << endl;
	return 0;
}
#endif