백준 1615 - 교차개수세기

백준 1615 - 교차개수세기

교차 그래프가 주어지고 몇개의 간선이 교차하는지 알아내야 한다.

어느 쪽 노드 집합을 기준으로 정렬을 한 후 반대 쪽 노드 집합들의 나열 형태를 보면서 교차 간선의 개수를 세보자.

그러면 inversion counting의 형태를 띄는 것을 관찰할 수 있다.

자세한 설명은 동일한 유형의 문제 풀이를 참조하라.

그대로 inversion counting의 개수를 출력해주면 된다.

전체 코드

from http://nicotina04.tistory.com/153 by ccl(A) rewrite - 2021-08-18 20:00:15