[BOJ] 10875 : 뱀

#include <stdio.h>
#include <vector>
#include <algorithm>
#define pb push_back
using namespace std;

const int INF = 2e9;
const int dx[] = { 1,0,-1,0 };
const int dy[] = { 0,-1,0,1 };

int l, n, x, y, nx, ny, dir;
long long ans;

struct line {
	int x1, y1, x2, y2;
	int dir;

	line(int a, int b, int c, int d) : x1(a), y1(b), x2(c), y2(d) {
		dir = (y1 == y2) ? 0 : 1; // 0이면 가로, 1이면 세로인 선분
		if (x1 > x2) swap(x1, x2);
		if (y1 > y2) swap(y1, y2);
	}
};
vector<line> lines;

// 뱀의 머리 방향으로 직진했을 때, 다른 선분들과 교차하기까지 걸리는 시간들의 최솟값
// 교차 안 하면 INF를 리턴
int check() {
	int ret = INF;
	for (auto prv : lines) {
		if (prv.dir == 0) {
			switch (dir) {
			case 0:
				if (y == prv.y1 && x < prv.x1)
					ret = min(ret, prv.x1-x);
				break;
			case 1:
				if (prv.x1 <= x && x <= prv.x2 && prv.y1 < y)
					ret = min(ret, y-prv.y1);
				break;
			case 2:
				if (y == prv.y1 && prv.x2 < x)
					ret = min(ret, x-prv.x2);
				break;
			case 3:
				if (prv.x1 <= x && x <= prv.x2 && y < prv.y1)
					ret = min(ret, prv.y1-y);
				break;
			}
		}
		else {
			switch (dir) {
			case 3:
				if (x == prv.x1 && y < prv.y1)
					ret = min(ret, prv.y1-y);
				break;
			case 2:
				if (prv.y1 <= y && y <= prv.y2 && prv.x1 < x)
					ret = min(ret, x-prv.x1);
				break;
			case 1:
				if (x == prv.x1 && prv.y2 < y)
					ret = min(ret, y-prv.y2);
				break;
			case 0:
				if (prv.y1 <= y && y <= prv.y2 && x < prv.x1)
					ret = min(ret, prv.x1-x);
				break;
			}
		}
	}
	return ret;
}

int main() {
	scanf("%d %d", &l, &n);

	// 테두리
	int a = -l-1, b = l+1;
	lines.pb({ a,a,a,b }); lines.pb({ a,a,b,a });
	lines.pb({ a,b,b,b }); lines.pb({ b,a,b,b });

	// 뱀이 끝까지 살아남을(?) 수 있으니 마지막은 INF로 한 번 더
	for (int i = 0; i <= n; i++) {
		int	t = INF; char d;
		if (i < n) scanf("%d %c", &t, &d);

		int ret = check();
		// 최단 부딪힘(?) 시간이 뱀이 움직이는 시간보다 짧거나 같으면 끝
		if (ret <= t) {
			return ~printf("%lld", ans + ret);
		}
		ans += t;
		nx = x+t*dx[dir], ny = y+t*dy[dir];
		dir = (d == 'L') ? (dir+3)%4 : (dir+1)%4;
		lines.pb({ x, y, nx, ny });
		x = nx, y = ny;
	}

	return 0;
}