สมมติมีจุดหลายๆ จุดอยู่บนพื้นที่

เราต้องวางสี่เหลี่ยมจตุรัสจำนวน k อัน

เพื่อครอบคลุมจุดทั้งหมด โดยต้องวางขนานกับแกน x y

คำถามคือ ต้องใช้สี่เหลี่ยมขนาดเล็กที่สุดขนาดเท่าไหร่ถึงจะครอบคลุมจุดทั้งหมด

อ่านเพิ่มเติม ที่นี่



เนื่องจากโจทย์กำหนดว่า ขนาดของพื้นที่ที่ใหญ่ที่สุดคือ 64,000

ดังนั้น วิธีการแก้ปัญหาคือ Binary Search

เราแค่ต้องหาว่า สี่เหลี่ยมขนาด x จำนวน k อัน จะครอบคลุมจุดทั้งหมดได้หรือไม่



เริ่มจาก ประกาศ function

let solve sets sqrs =

sets คือจุดต่างๆ

sqrs คือจำนวนสี่เหลี่ยมจตุรัส



ถัดมาคือ function เพื่อหาว่าสี่เหลี่ยมจตุรัสจะสามารถครอบคลุมจุดทั้งหมดได้หรือไม่

let matchSqr size =
    let rec matchSqrX sets sqrs =
        if Set.count sets <= sqrs then
            Seq.singleton size
        elif sqrs = 0 then
            Seq.empty

function ชื่อ matchSqr

size คือขนาดของสี่เหลี่ยมจตุรัส



เราสร้างอีก function (matchSqrX) เพื่อทำ recursive

ถ้า จำนวนจุดที่เหลือ (sets) <= จำนวนสี่เหลี่ยม (sqrs)

หมายความว่าเราสามารถใช้สี่เหลี่ยมหนึ่งอัน ต่อหนึ่งจุด และได้คำตอบทันที

แต่ถ้า จำนวนสี่เหลี่ยม (sqrs) เหลือ 0 แปลว่าไม่มีคำตอบ



function ยังไม่จบ มีต่อ

        else 
            let x,y = Set.minElement sets
            let ys1 = sets |> Seq.filter (fun (x2,y2) -> x2 > x && x2 <= x+size &&
                                                         y2 >= y-size && y2 <= y)
                           |> Seq.map snd
                           |> Set.ofSeq
            let ys2 = sets |> Seq.filter (fun (x2,y2) -> x2 > x && x2 <= x+size &&
                                                         y2 >= y && y2 <= y+size)
                           |> Seq.map snd
                           |> Seq.map (fun y2 -> y2 - size)
                           |> Set.ofSeq
            let ys = ys1 + ys2 + Set.singleton y
            seq {
               for y in ys do
               let coveredSet = sets |> Seq.filter (fun (x2,y2) -> x2 >= x && x2 <= x+size &&
                                                                   y2 >= y && y2 <= y+size)
                                     |> Set.ofSeq
               for i in matchSqrX (sets-coveredSet) (sqrs-1) do
               yield i
            }
    matchSqrX sets sqrs

ตอนแรก เราดีงเฉพาะจุดที่น้อยที่สุด (x,y) ออกมาจาก sets

เนื่องจาก x น้อยที่สุด เราแน่ใจได้เลยว่ามันจะเป็นจุดที่อยู่ซ้ายที่สุด

เราสามารถวางสี่เหลี่ยมชนจุดทางด้านซ้ายได้เลย



ต่อมาเราก็เลื่อนสี่เหลี่ยมไปบนสุด คือด้านล่างของสี่เหลี่ยมชนจุด y

แล้วเราก็ list จุด y ต่างๆ ที่เจอออกมา (ys1)

เช่นเดียวกัน ทีนี้ลองเลื่อนสี่เหลี่ยมไปล่างสุด ด้านบนของสี่เหลี่ยมชนจุด y

แล้วเราก็ list จุด y ต่างๆ ออกมา (ys2)



ys ก็คือจุด y ทั้งหมดที่สี่เหลี่ยมจะเลื่อนขึ้นและลงได้

ทีนี้ก็ loop เลยครับ ลองทุกวิธี

coveredSet คือ จุดที่โดนครอบโดยสี่เหลี่ยม

แล้วเราก็ recursive เพื่อลองต่อไป



สุดท้าย ก็หาขนาดที่เล็กที่สุดด้วย binary search

let rec binarySearch min max =
    if min = max then
        max
    else 
        let mid = (min + max) / 2
        let result = matchSqr mid
        if Seq.isEmpty result then
            binarySearch (mid+1) max
        else
            binarySearch min mid
binarySearch 1 64000 |> string

จบ