고랑에 갇히다

농부 존은 최근에 농장의 크기를 늘렸고, 소들의 관점에서 농장은 이제 사실상 무한한 크기가 되었다! 소들은 농장의 방목지를 맛있는 풀로 가득 찬 정사각형 "칸"들로 이루어진 무한한 2차원 격자로 생각한다(각 칸을 무한한 체스판의 한 칸이라고 생각하면 된다). 농부 존의 소 \(N\)마리(\(1\le N\le 50\))는 각각 서로 다른 칸에서 출발하며, 일부는 북쪽을, 일부는 동쪽을 향한 채 시작한다.

매시간 각 소는 다음 중 하나를 한다.

• 현재 칸의 풀이 이미 다른 소에게 먹혔다면 멈춘다.
• 현재 칸의 풀을 모두 먹고, 자신이 향한 방향으로 한 칸 전진한다.

따라서 시간이 지나면서 각 소는 자신의 뒤에 빈 칸들로 이루어진 황폐한 "고랑"을 남긴다.

두 소가 같은 이동에서 풀이 있는 같은 칸으로 들어오면, 그 칸을 공유하고 다음 시간에 각자의 방향으로 계속 이동한다.

각 소가 먹는 풀의 양을 구하시오. 어떤 소들은 결코 멈추지 않으며, 따라서 무한한 양의 풀을 먹는다.

문제 제공: Brian Dean

배점

• 테스트 케이스 2-5에서 모든 좌표는 \(100\) 이하이다.
• 테스트 케이스 6-10에는 추가 제약이 없다.

문제 제공: Brian Dean

입력의 첫째 줄에 \(N\)이 주어진다. 다음 \(N\)개의 줄 각각에 소 한 마리의 시작 위치가, N(북쪽 방향) 또는 E(동쪽 방향)인 문자 하나와 칸의 좌표를 나타내는 두 음이 아닌 정수 \(x\)와 \(y\)(\(0\le x\le 10^9\), \(0\le y\le 10^9\))로 주어진다. 모든 \(x\)좌표는 서로 다르며, \(y\)좌표도 마찬가지이다.

\(N\)개의 줄을 출력한다. 출력의 \(i\)번째 줄은 입력의 \(i\)번째 소가 먹는 풀의 칸 수를 나타내야 한다. 소가 무한한 양의 풀을 먹는다면 그 소에 대해 "Infinity"를 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2020-2021 > December > Bronze