2643 : 수족관1
- 제한시간
- 1000 ms
- 메모리제한
- 128 MB
- 해결횟수
- 52 회
- 시도횟수
- 140 회
문제
아래 그림 1은 수족관을 앞에서 본 모양이다. 이 수족관에는 물이 가득 차 있다.
만약 수족관 밑바닥(수평선분)에 구멍을 하나 뚫으면, 구멍을 통해 수족관의 물이 빠지게 된다.
그림 1의 수족관의 경계는 4개의 꼭짓점으로 표현된다. 각 꼭짓점의 위치는 세로줄 번호와 가로줄 번호로 나타낸다.
수족관의 바닥을 나타내는 수평선분에 구멍이 있다면,
수족관에 담긴 물의 양은 물이 차지하는 면적과 일치하는 양이다.
물의 양의 단위는 L(리터)이다. 따라서 그림 1에서 가득 담긴 물의 양은 물이 차지하는 면적과 동일한 40L이다.
그림 2처럼 수족관의 바닥이 복잡할 수도 있다.
수족관의 바닥은 수평선분과 수직선분이 번갈아 여러 번 나타나는 형태이다.
구멍은 항상 수평선분에만 존재하며, 수평선분의 한 가운데에 위치한다.
물이 가득 찬 수족관의 바닥 모양과 구멍이 뚫려있는 수평선분들이 주어지면,
입력형식
입력의 첫 줄은 수족관의 경계에 있는 꼭짓점의 개수 N(4≤N≤5,000)이 주어진다.N은 짝수이다.
수족관의 경계는 항상 꼭짓점 (0, 0)부터 시작한다. 그리고 마지막 꼭짓점은 (A, 0)의 형태로 끝난다.
즉, 시작 꼭짓점과 마지막 꼭짓점의 가로줄 번호는 항상 0이다.
수족관의 경계를 이루는 변은 꼭짓점 (0, 0)부터 시작하는 데,
수직선분으로 시작하여 수평선분과 수직선분이 번갈아가며 반복되다 수직선분으로 끝난다.
따라서 수직선분이 수평선분보다 항상 하나 더 많다.
두 번째 줄부터 N개의 줄에는 수족관 경계에 있는 N개의 꼭짓점의 세로줄 번호와 가로줄 번호가 빈칸을 사이에 두고
각 줄에 하나씩, 첫 꼭짓점 (0, 0)부터 시계 반대방향을 따라 차례로 주어진다.
세로줄과 가로줄 번호의 범위는 0 이상 40,000 이하의 정수이다.
다음 줄에는 수족관의 수평선분에 위치한 구멍의 개수 K(1 ≤ K < N/2)가 자연수로 주어진다.
다음 K개의 줄에는 각 구멍이 존재하는 수평선분의 양 끝 꼭짓점 위치를 나타내는
네 개의 값이 빈 칸을 사이에 두고 차례로 주어진다.
즉, 어떤 구멍이 위치한 수평선분의 정보가 a b c d로 주어졌다면,
구멍이 위치한 수평선분은 꼭짓점 (a, b)와 꼭짓점 (c, d)를 연결한 선분이라는 의미이다.
항상 a < c이다.
<제약조건>
• 부분문제 1: 전체 점수 100점 중 23점에 해당하는 데이터에 대해, N=6, 세로줄, 가로줄의 번호 ≤ 10 이다.
• 부분문제 2: 전체 점수 100점 중 19점에 해당하는 데이터에 대해, N≤10, K=1, 세로줄, 가로줄의 번호 ≤100 이다.
• 부분문제 3: 전체 점수 100점 중 22점에 해당하는 데이터에 대해, K≤100, 세로줄, 가로줄의 번호 ≤500 이다.
• 부분문제 4: 전체 점수 100점 중 36점에 해당하는 데이터에 대해, 추가 제약 조건이 없다.
출력형식
출력은 단 한 줄이며, 구멍을 통해 물이 빠져 나간 후,
수족관에 남아 있는 물의 양을 0 이상의 정수로 출력한다.
입력 예4 0 0 0 5 8 5 8 0 1 0 5 8 5 |
출력 예0 |
입력 예14 0 0 0 5 1 5 1 3 2 3 2 4 3 4 3 2 5 2 5 4 6 4 6 3 8 3 8 0 2 1 3 2 3 3 2 5 2 |
출력 예7 |