시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 44 23 19 54.286%

문제

출제진 onionpringles는 9월 10일 그의 마지막 문제를 출제한 뒤 9월 11일 호국 요람으로 떠났다. 슬프게도, 그가 들어간 부대엔 이상한 선임이 많았다. 그가 KAIST 수리과학과 출신임을 알게 된 선임 중 하나는 그에게 다음과 같은 요구를 했다.

“우리가 지금 텐트를 하나 쳐야 되거든? 저기 평행하게 있는 밧줄 두개랑 중간 중간 말뚝 박혀 있는거 보이지? 저기서 말뚝 4개 골라서 그거대로 텐트를 칠거야. 근데 우리 부대는 텐트 밑바닥을 무조건 밑각이 둘 다 예각이거나 윗각이 둘 다 예각인 사다리꼴로 치는 전통이 있어. 전통 지키는 텐트 아무거나 계속 만들어봐. 내 마음에 들면 그만하게 해줄게.”

눈앞이 캄캄해진 양파는 최악의 경우 자신이 서로 다른 텐트를 몇개나 만들어봐야 되는지 계산하기 시작했다. 불쌍한 양파를 위해 서로 다른 텐트의 개수라도 당신이 세어주자. 텐트의 바닥을 구성하는 말뚝의 집합이 같으면 같은 텐트이다.

위의 그림은 간단한 예시를 나타낸다. 위쪽의 두 그림은 조건을 만족하지 않고, 아래쪽의 두 그림은 조건을 만족한다.

입력

첫 번째 줄에 두 직선 위의 말뚝의 개수 N, M과 밧줄의 y좌표 y1, y2가 공백을 사이에 두고 주어진다. (2<= N,M <=100,000, -1,000,000,000 <= y1, y2 <= 1,000,000,000, y1 ≠ y2)

다음 N개의 줄은 위쪽 밧줄 위에 있는 말뚝의 x좌표를 나타내는 정수가, 그 다음 M개의 줄은 아래쪽 밧줄 위에 있는 말뚝의 x좌표를 나타내는 정수가 한줄에 하나씩 주어진다. x좌표의 범위는 -1,000,000,000 이상 1,000,000,000 이하이다. 같은 말뚝이 중복되어 주어지는 경우는 없다.

출력

가능한 사다리꼴의 개수를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

2 3 33 12
-1
1
-2
0
2

예제 출력 1

1

출처

University > KAIST > 2017 KAIST 7th ACM-ICPC Mock Competition L번

  • 문제의 오타를 찾은 사람: jh05013
  • 문제를 만든 사람: wwiiiii