이동식 저장소

1615번: 교차개수세기 첫 줄에 N과 간선의 개수 M이 주어진다. 그 다음 줄부터 M+1번째 줄까지 두 개의 수(i, j)가 주어지는데 이는 왼쪽 그룹의 i번 정점과 오른쪽 그룹의 j번 정점을 연결하는 간선이 있다는 의미이다. www.acmicpc.net 뭔가 많이 본 듯한 문제이다. 어디서 봤나 했더니 2568번 전깃줄 문제와 매우 유사하다. 물론 풀이가 유사하다는 건 아니고 그림이 비슷하다는 소리. 이 문제에서는 전깃줄이 교차하는 횟수를 세어야 한다. 문제에 두 전깃줄이 교차하는 조건이 주어져 있는데, 계산의 편의를 위해 왼쪽에 있는 정점을 오름차순으로 살펴보면서, 각 정점의 전깃줄이 다른 전깃줄과 몇 번 교차하는지 계산해 보자. 왼쪽 정점 $i$와 오른쪽 정점 $j$에 연결된 전깃줄을 $(i, ~..