Problemas
혼돈의 도시는 점점 통제 불능이 되어간다. 건물들이 여기저기 건설되어 도시 구조가 엉망이 되었다. 시장은 도시 계획을 세우기로 했다. 뉴욕의 맨하튼처럼, 건물들을 직사각형으로 하고 동서, 남북 방향으로 바둑판식 도로 구조를 갖는 것이 좋다는 결과가 나왔다.
이미 건물들은 마구잡이로 세워졌다. 각 건물들은 격자 하나를 채우고 있다. 바둑판식 도로를 깔면서 몇몇 도로가 놓일 위치에 있는 건물들은 해체시켜야 한다. 가장 최소의 건물을 파괴하고자 한다.
위의 그림은 문제의 상황을 보여준다. 도로는 일정한 간격 D로 동서, 남북으로 난다. 도로는 격자 한 칸 만큼의 폭을 갖는다.
Entrada
입력에는 먼저 D N이 주어진다(1≤D≤1,000 and 0≤N≤100,000). N은 이미 건설된 건물의 수이다.
다음 N 줄에 걸쳐서 각 건물의 위치 좌표 xi yi가 입력된다. (-109≤xi yi≤109)
Salida
파괴해야 할 최소 건물의 수를 출력하라.
Ejemplo
3 10
1 0
2 0
3 0
4 0
1 2
0 3
1 5
3 5
4 2
-2 2
1
Fuente
BAPC 2006,poj 3060
Debes iniciar sesión para escribir código.