16444번 - Cortador de Pizza
Giuseppe는 선물로 피자 커터를 받았고, 이를 기념하여 직사각형 모양의 피자를 구웠습니다.Giuseppe는 피자를 항상 연속된 선으로 자르며 (직선일 필요는 없습니다), 모든 선은 아래 둘 중 하나에 속합니다.
Giuseppe는 평소 피자를 자를 때 이동 방향이 같은 선들이 만나지 않도록 피자를 자릅니다.[사진에서 왼쪽 경우를 참고하세요.]
하지만 Giuseppe는 기하와 위상수학, 그리고 조합론을 좋아하기 때문에, 만약 이동 방향이 같은 선들끼리 만날 수 있다면 동일한 횟수로 잘라서 더 많은 조각을 만들 수 있다는 것을 알고 있습니다.[사진에서 오른족 경우를 참고하세요.]
물론, 그렇다고 아무렇게나 피자를 자르지는 않고, 피자를 자르는 선들에 아래 제약 조건을 걸었습니다.
각 선의 시작점과 끝점이 주어질 때, 이 방식대로 자르면 Giuseppe가 피자를 몇 조각으로 나누게 될 지 출력하세요.
첫째 줄에는 피자의 가로 길이 X와 세로 길이 Y가 주어집니다. (1 ≤ X, Y ≤ 109)이 때 피자는 (0, 0)과 (X, Y)를 두 꼭짓점으로 하는 축에 평행한 직사각형이 됩니다.
둘째 줄에는 가로로 자르는 선의 개수 H와 세로로 자르는 선의 개수 V가 주어집니다. (1 ≤ H, V ≤ 105)
이어 H개의 줄에 걸쳐 가로로 자르는 선의 시작점과 끝점의 y좌표가 주어집니다. (1 ≤ y < Y)
이어 V개의 줄에 걸쳐 세로로 자르는 선의 시작점과 끝점의 x좌표가 주어집니다. (1 ≤ x < X)
Giuseppe가 피자를 몇 조각으로 나누게 될 지 출력하세요.
댓글을 작성하려면 로그인해야 합니다.
hibye1217 3년 전
문제
Giuseppe는 선물로 피자 커터를 받았고, 이를 기념하여 직사각형 모양의 피자를 구웠습니다.
Giuseppe는 피자를 항상 연속된 선으로 자르며 (직선일 필요는 없습니다), 모든 선은 아래 둘 중 하나에 속합니다.
Giuseppe는 평소 피자를 자를 때 이동 방향이 같은 선들이 만나지 않도록 피자를 자릅니다.
[사진에서 왼쪽 경우를 참고하세요.]
하지만 Giuseppe는 기하와 위상수학, 그리고 조합론을 좋아하기 때문에, 만약 이동 방향이 같은 선들끼리 만날 수 있다면 동일한 횟수로 잘라서 더 많은 조각을 만들 수 있다는 것을 알고 있습니다.
[사진에서 오른족 경우를 참고하세요.]
물론, 그렇다고 아무렇게나 피자를 자르지는 않고, 피자를 자르는 선들에 아래 제약 조건을 걸었습니다.
각 선의 시작점과 끝점이 주어질 때, 이 방식대로 자르면 Giuseppe가 피자를 몇 조각으로 나누게 될 지 출력하세요.
입력
첫째 줄에는 피자의 가로 길이 X와 세로 길이 Y가 주어집니다. (1 ≤ X, Y ≤ 109)
이 때 피자는 (0, 0)과 (X, Y)를 두 꼭짓점으로 하는 축에 평행한 직사각형이 됩니다.
둘째 줄에는 가로로 자르는 선의 개수 H와 세로로 자르는 선의 개수 V가 주어집니다. (1 ≤ H, V ≤ 105)
이어 H개의 줄에 걸쳐 가로로 자르는 선의 시작점과 끝점의 y좌표가 주어집니다. (1 ≤ y < Y)
이어 V개의 줄에 걸쳐 세로로 자르는 선의 시작점과 끝점의 x좌표가 주어집니다. (1 ≤ x < X)
출력
Giuseppe가 피자를 몇 조각으로 나누게 될 지 출력하세요.