在猴猴共和國的成功街，流傳著一個古老的傳說。據說，這條街道的土地上藏著一個神秘的寶藏，而尋找這個寶藏的關鍵就在於一片神奇的藏寶圖上。
數百年前，一名猴猴國的國王曾經向一位智慧的長者尋求幫助。他想知道如何找到這個傳說中的寶藏，但長者告訴他，要找到寶藏，首先必須解決在藏寶圖裡的複雜謎題。
謎題是這樣的：在這張藏寶圖上，有$N$個神秘的整數點，每個點都可能是找到寶藏的線索。但為了找到寶藏，必須以特定的方式覆蓋這些點。具體來說，必須使用兩個邊長均為$K$的正方形，且兩個正方形之間需互相獨立、不能相交(邊界和端點相交都不行)且四條邊須跟座標軸平行，並最大化的覆蓋神秘點(點在正方形邊界上算覆蓋)。只有在這樣的情況下，才能確保寶藏的位置被完全包圍，並將其揭示出來。
為了達成這個目標，猴猴國的人們開始努力試著破解這個謎題，他們不斷地在平面上標記可能的點，嘗試不同的正方形配置，以最大程度地覆蓋這些點。他們希望能夠解開這個謎題，找到寶藏，並讓成功街重新閃耀光彩。然而經過了數百年，謎題仍然未被破解。
現在，這個解開這個問題的重責大任交到了你的手上，請你幫助他們解決這個謎題：在平面藏寶圖上，不相交的兩個正方形，最多共能覆蓋多少個點。解開這個謎題將能夠傳說中的找到神秘寶藏，並為成功街的未來帶來新的希望。
第一行有兩個正整數$N,K$，分別代表點的數量與正方形的邊長。
接下來有$N$行，每行有兩個整數$x,y$，代表有一個點在座標$(x,y)$上，點的座標不會重複。
測資限制
$N,K$為正整數
$N \leq 2000$
$K \leq 10^9$
$-10^9 \leq$ 點的座標值域 $\leq 10^9$
輸出一行包含一整數，代表的意義如題目所述。
7 1 1 1 1 2 2 1 2 2 2 3 3 2 3 3
6
5 3 1 1 4 2 7 0 5 5 5 -1
4
5 9 0 0 1000000000 1000000000 999999999 999999991 -10 -1 -1 -2
4
本題共有四組子任務，條件限制如下所示。
子題一 16%
$N \leq 100$
子題二 20%
$N \leq 500$
子題三 26%
$K \leq 10^3$
$-10^3 \leq$ 點的座標值域 $\leq 10^3$
子題四 38%
無額外限制
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||