| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 13 | 5 | 4 | 66.667% |
Одна из центральных площадей Архангельска замощена прямоугольными плитками размера 1ドル \times k$. Если ввести систему координат, так что левый нижний угол одной из плиток будет иметь координаты $(0, 0),ドル то левые нижние углы плиток будут иметь координаты $(i \cdot k+j,j)$ для всех целых $i$ и $j$.
На площади было решено установить памятник известному архангельскому писателю и художнику Степану Писахову. Для установки памятника необходимо удалить все плитки, полностью или частично попадающие под его основание. Основание памятника имеет форму многоугольника с целочисленными координатами вершин, все стороны которого параллельны осям координат. Известно, что любая прямая, пересекающая основание памятника и параллельная одной из осей координат, в пересечении с основанием образует один отрезок.
Для установки памятника необходимо выбрать место на площади таким образом, чтобы количество удалённых плиток было минимальным. При выборе места основание разрешается только передвигать параллельно осям координат.
Требуется написать программу, вычисляющую минимальное количество плиток, которые придётся удалить.
Первая строка входных данных содержит два числа $n$ и $k$ --- количество вершин в основании памятника и размер плитки.
Каждая из последующих $n$ строк содержит два целых числа $x_i,ドル $y_i$ --- координаты $i$-й вершины основания. Координаты перечислены в порядке обхода против часовой стрелки.
Единственная строка выходных данных должна содержать минимально возможное количество плиток, которые необходимо удалить для размещения памятника на площади.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 32 | 1ドル \le n \le 50,ドル 1ドル \le k \le 50,ドル 0ドル \le x_i, y_i \le 50$ |
| 2 | 37 | 1ドル \le n \le 1000,ドル 1ドル \le k \le 1000,ドル 0ドル \le x_i, y_i \le 1000$ |
| 3 | 31 | 1ドル \le n \le 100,000円,ドル 1ドル \le k \le 100,000円,ドル 0ドル \le x_i, y_i \le 1000,000円$ |
12 3 2 3 1 3 1 2 3 2 3 1 8 1 8 2 10 2 10 3 8 3 8 4 2 4
7
Исходное расположение основания памятника в первом примере.
Оптимальное расположение основания памятника в первом примере.