아무도 안올리셔서 제가 씁니다 :)

  A. How Big Are the Pockets?

   [문제 설명]

  Polygonovich 교수는 평면 상의 위치에서 랜덤하게 걸어다니는것을 즐긴다. 교수는 아침에 원점에서 북쪽을 바라보며 긴 여행을 떠난다. 교수는 직진하거나 왼쪽으로 90도 회전, 오른쪽으로 90도 회전만 하면서 여행을 즐긴다. 이 여행동안 한번 방문했던 점을 두번 다시 방문하지 않으며, 해가 지기 전에 시작했던 위치로 돌아온다. 따라서 교수가 지나간 경로는 연결하면 하나의 도형을 만들게 된다. (아래 그림 참조)

  
  
 교수가 한 바퀴 돌고 온 구간이 위의 그림과 같다고 하자. 당신은 이 구간이 convex가 아니라는 것을 깨달았다. 따라서 아래와 같이 "pocket" 을 채워서 convex로 만들려고 한다.


 아래의 둘 중 하나를 만족하면 "pocket" 이라고 부른다.

 1) 한 점을 기준으로 위-아래가 막혀있으면 이 점은 pocket이다. 
 2) 한 점을 기준으로 왼쪽-오른쪽이 막혀있으면 이 점은 pocket이다.

 따라서 첫 번째 그림에서 x는 2)를, y는 1), 2)를, z)는 1)을 만족하므로 이 세 점은 pocket이고, w는 둘 다 만족하지 않으므로 pocket이 아니다.

 교수가 이동한 경로가 입력으로 주어질 때, "pocket"의 크기를 출력하는 프로그램을 작성하시오.

  Small Data Set) 각 좌표의 절대값은 100 이하
  Large Data Set) 각 좌표의 절대값은 3000 이하

  

[문제 풀이]

  Small Data Set의 경우에는 좌표의 절대값이 작기 때문에, 배열로 표현할 수 있습니다. 아래의 그림을 살펴보도록 하지요.



  위와 같이 좌표를 변형합니다. 즉, 모든 좌표를 2배해서 점선부분까지 배열에 채우는 것이지요. 이렇게 2배씩 해주는 이유는, 내부/외부의 점을 쉽게 체크하기 위해서 입니다. 이렇게 해서 내부/외부를 나눴다면 문제에서 정의한 pocket의 수를 찾으면 해결할 수 있습니다. 내부가 아닌 모든 점에 대하여 현재 점이 pocket인지 찾으면 됩니다. 케이스 하나에 대하여 최대 400 * 400 * 400 정도의 연산이면 답을 구할 수 있지요. 소스코드에 간단한 주석을 달아두었습니다 :D

  하지만 Large Data Set은 좌표의 절대값이 너무 크지요. 따라서 각 점에 대하여 직접 pocket을 구하는 위의 알고리즘으로는 무리가 있습니다. 따라서 현재 점이 pocket인지 아닌지를 빨리 계산하면 되지요.  임의의 어떤 점에서 그 점의 왼쪽에 polygon 내부점이 존재하는가? 오른쪽에 내부점이 존재하는가? 위쪽은? 아래쪽은? 이라는 4가지의 질문을 바로바로 대답할 수 있다면 pocket인지 아닌지를 알 수 있지요.
 
  만약 (x, a)라는 점이 내부점이고, (x, b)라는 점이 내부점이라면, a <= c <= b를 만족하는 모든 c에 대하여 (x, c)가 내부점이나 pocket이 된다는 점을 알 수 있습니다. 이는 90도 회전하여 y좌표에 대해서도 마찬가지이지요. 즉 모든 좌표에 대하여 현재 점이 내부점이냐? pocket이냐? 둘 다 아니냐?를 O(1)만에 계산할 수 있게 된 셈입니다.

  Large Data Set은 직접 테이블로 표현할 수 없습니다. 하지만 모든 점에 대하여 이 점이 내부점 or pocket인지를 구할 수 있고요. 입력받은 다각형이 있을 때 내부 넓이는 따로 구해야 합니다. 다각형의 내부넓이를 구하는 알고리즘은 검색하면 금방 나올테니 여기에다가 쓰진 않겠습니다 :)

  B. Portal

   [문제 설명]
 
  Portal은 1인칭 퍼즐 게임으로, 이 게임의 주인공은 벽에 두 개의 포탈을 만들어서, 한쪽 포탈에 들어가면 반대쪽 포탈로 나올 수 있다. 이 문제는 비슷한 아이디어에서 출발한다.

  (R, C) 크기의 격자판이 있다. 당신은 이 격자판 어딘가에 위치해 있고, 또 다른 위치에는 맛있는 케이크가 놓여져 있다. 당신은 매우 배가 고프기 때문에 최대한 빨리 이 케이크를 먹고 싶어한다. 당신은 현재 위치에서 동서남북 네 방향으로 이동할 수 있으며, 당신에게는 Portal Gun이 있어 포탈을 만들어서 이동할 수도 있다.

  당신을 Portal Gun을 이용하여 두 가지 포탈 (노란색, 파란색)을 만들 수 있으며, 무조건 직진하는 성질을 가지고 있다. 또한 케이크가 있더라도 그대로 투과하는 성질을 가지고 있다. 다만 Portal Gun은 동서남북 네 방향으로만 발사할 수 있다.

  노란색과 파란색 포탈을 만들었다면, 당신은 이 포탈을 통해 이동할 수 있다. 노란색 포탈로 들어갔다면 파란색 포탈로 나오게 되며, 그 반대의 경우도 성립한다. 당신은 Portal Gun을 사용함으로써 더 빨리 케이크를 먹을 수 있게 될 수 있을 것이다! 

   아래의 그림을 살펴보자. 

  회색 칸은 벽을 나타내고 흰색 칸은 아무것도 없는 빈 공간을 나타낸다. 또한 빨간색 점은 당신의 위치이다.

  오른쪽을 향해 파란색 포탈 건을 발사하면 위의 그림과 같이 파란색 포탈이 생긴다.

  아래쪽을 향해 노란색 포탈 건을 발사한 후의 상태이다.

   남쪽으로 한번 이동하였다.

  한번 더 남쪽으로 이동하였다. 아래쪽의 노란색 포탈을 통해 파란색 포탈로 순간이동하게 되었다.

  똑같은 색깔의 포탈은 최대 1개만 존재한다. 현재 위치에서 파란색 포탈을 왼쪽으로 쏘면 위의 그림과 같이 된다.

  포탈은 무조건 벽에만 만들 수 있으며, 포탈이 없는 벽으로는 이동할 수 없다. 포탈 건을 사용하는 것은 이동횟수로 세지 않는다고 가정한다. 케이크를 먹을 수 있는 최소 이동횟수를 구하시오.

  Small Data Set) 최대 Grid 크기는 8 x 8
  Large Data Set) 최대 Grid 크기는 15 x 15

  C. No Cheating

   [문제 설명]
 
  기말고사를 앞두고 있는 알고스팟 고등학교에서는 몇 명의 학생이 수시로 치팅을 시도한다는 정보를 입수했다. 그래서 이 학교의 교장인 JM은 이러한 부정행위를 방지하는 자리배치를 하려고 한다. 이 클래스룸은 M개의 행 N개의 열로 구성되어 있으며 각각의 칸에 책상들이 배치되어 있다. 다만 일부 책상은 파손되어 배치할 수 없게 되어 있다.

  각 학생은 자기 자리로부터 왼쪽, 오른쪽, 왼쪽 앞, 오른쪽 앞 자리의 시험지를 볼 수 있다. 따라서 어떤 자리에 학생을 위치시켰다면 A,C,D,E 위치에는 배치할 수 없다.



  한 교실의 배치도가 주어져 있을 때, 이 교실에서 최대 몇 명의 학생이 시험을 볼 수 있는지 구하시오. 물론 모든 학생이 치팅할 수 없는 위치에 있어야 한다.  

  Small Data Set) 최대 교실 크기는 10 x 10
  Large Data Set) 최대 교실 크기는 80 x 80

  D. Endless Knight

   [문제 설명]
 
  체스의 Knight는 L자 모양으로 점프할 수 있는 말이다. (r1, c1)에서 (r2, c2)로 점프할 수 있다는 뜻은 (r1 - r2)^2 + (c1 - c2)^2 = 5를 만족하는 것과 같은 의미를 가진다.

  이 문제에서는 왼쪽 위 좌표(1, 1)에서 출발하여 (H, W)까지 이동하는 것이 목표이다. 또한 이 문제에서 적용되는 두 가지 제약조건이 있는데, 첫 번째 조건은 Knight는 반드시 x,y 좌표가 증가하는 방향으로만 이동하여야 한다. 즉 (1, 2)로 이동하거나 (2, 1)로 이동하여야 한다. [ (1, -2)나 (2, -1)은 잘못된 이동이다. ] 두 번째 조건은 Knight가 절대로 갈 수 없는 바위가 R개(R <= 10) 있다는 점이다.

  당신은 (1, 1)에서 (H, W)까지 가는 경로의 수를 구하고 싶어한다. 다만 이 수는 매우 크기 때문에 10007로 나눈 나머지를 구하려고 한다. 참고로 10007은 소수(Prime Number)이다.

  Small Data Set) H, W <= 100
  Large Data Set) H, W <= 100,000,000