問題
오늘도 열심히 공부하던 진돌이는 좌표평면에 수많은 수직/수평 선분들을 그리느라 지쳐버렸다. 특히 펜을 들었다 뗐다 하는 일이 너무나 귀찮았던 진돌이는 될 수 있으면 펜을 조금 들었다 놓으면서 모든 선분들을 그리고 싶었다.
예를 들어, 5개의 선분으로 구성된 아래 그림을 보면
펜을 한 번도 떼지 않고 똑같이 그릴 수 있다. 따라서 펜을 뗀 횟수는 0회이다. 그런데 문제는 진돌이가 가진 펜의 두께가 너무 얇아서 같은 선분을 여러 번 색칠해야 할 것 같다. 반복해서 색칠할 횟수와 선분들이 주어질 때 펜을 최소한 몇 번 들었다 놓아야 하는가?
단, 선분들이 겹쳐도 알아내고자 하는 건 선분들이 이루는 모양이기 때문에 여러 번 덧칠할 필요는 없다.
入力
첫 행에는 두 자연수 선분의 수 N과 반복할 횟수 M이 주어진다. 선분의 수는 50개 이하이며, 반복할 횟수는 1,000,000번 이하이다.
다음 N 개의 행에 걸쳐 각 선분의 양 끝 점의 좌표가 주어진다. 좌표는 -1,000,000 이상 1,000,000 이하의 값이다. 모든 선분은 축에 대해 수직 또는 수평하다.
出力
최소 펜을 드는 횟수를 출력한다.
例題
2 1
-10 0 10 0
0 -10 0 10
1
出典
Online Contest
ログインしないとコードを書けません。