1115 : อุลตร้าแมน (Ultraman)
Problem type : Batch
Time limit : 2.0 second(s)
Memory limit : 128 megabyte(s)

       อุลตร้าแมนเป็นสัตว์สังคม (สิ่งมีชีวิตที่อยู่กันเป็นกลุ่ม) แน่ นอน ในกลุ่มของอุลตร้าแมนย่อมต้องมี “อุลตร้าแมนจอมโจรยอดนักฆ่า” ซึ่งสร้างความเดือดร้อนให้กับสังคมอุลตร้าแมนอย่างมาก ดังนั้นในกลุ่มของอุลตร้าแมนจึงได้มีการแต่งตั้ง “อุลตร้าแมนลาดตระเวน” เพื่อรักษาความปลอดภัยในชุมชนอุลตร้าแมน

            ลักษณะของหมู่บ้านอุลตร้าแมนจะประกอบด้วยบ้านครอบครัวอุลตร้าแมนทั้งสิ้น n หลัง และจะมี “อุลตร้าแมนลาดตระเวน” ทั้งสิ้น k คน ทำให้เราสามารถแบ่งบ้านครอบครัวอุลตร้าแมนทั้ง n หลัง ออกเป็น k กลุ่ม เพื่อให้อยู่ในความรับผิดชอบของ “อุลตร้าแมนลาดตระเวน” แต่ละบุคคล

            บ้านครอบครัวอุลตร้าแมนแต่ละหลังจะอยู่ในตำแหน่งพิกัด (x,y) เมื่อ x และ y เป็นจำนวนนับ บนกริดขนาด 1000*1000 ซึ่งจะทำให้บ้านแต่ละหลังจะมีทางเดินหากัน (เอดจ์) เชื่อมถึงกันโดยบ้านที่อยู่พิกัด (x1,y1) และ (x2,y2) จะมีระยะห่างกัน sqrt( (x1-x2)^2 + (y1-y2)^2 ) 

            สมมติ ให้ “อุลตร้าแมนลาดตระเวน” คนหนึ่งดูแลบ้านครอบครัวอุลตร้าแมน จำนวนหนึ่ง เราจะนิยาม “ค่าความเหนื่อยของอุลตร้าแมนลาดตระเวน” คนนี้ ให้มีค่าเท่ากับ ระยะห่างที่มากที่สุดเมื่อเราสร้างทางเชื่อมระหว่างบ้านครอบครัวอุลตร้าแม นทั้งสิ้น p-1 เส้นทาง (เมื่อมีบ้านครอบครัวอุลตร้าแมนทั้งสิ้น p หลัง) เพื่อเชื่อมบ้านครอบครัวอุลตร้าแมนทั้ง p หลังเข้าด้วยกัน (พูดง่ายๆคือระยะทางของเอดจ์ที่มากที่สุดเมื่อคุณสร้าง minimum spanning tree บนโหนดทั้ง p โหนดจากเอดจ์ทั้งสิ้น p*(p-1)/2 เอดจ์)

            เรากำหนดให้ค่าความเหนื่อยทั้งมวล ของเหล่า “อุลตร้าแมนลาดตระเวน” คือค่าความเหนื่อยที่มากที่สุดของ “อุลตร้าแมนลาดตระเวน” คนใดคนหนึ่ง

            กำหนดพิกัดของบ้านครอบครัวอุลตร้าแมนทั้ง n หลัง และจำนวนของ “อุลตร้าแมนลาดตระเวน” k จงหาค่าความเหนี่อยทั้งมวลที่น้อยที่สุด

ข้อมูลนำเข้า

บรรทัดแรกประกอบด้วยจำนวนนับ n และ k แทนจำนวนของบ้านครอบครัวอุลตร้าแมน และจำนวนของ “อุลตร้าแมนลาดตระเวน” ( 1 < k < n < 1000 )

ถัดมา n บรรทัดประกอบด้วยจำนวนนับ 2 จำนวน x และ y แทนพิกัดของบ้านครอบครัวอุลตร้าแมนแต่ละหลัง ( 1 < x, y < 1000 )

ข้อมูลส่งออก

บรรทัดแรกและบรรทัดเดียวแสดงค่า กำลังสอง ของค่าความเหนื่อยทั้งมวลของเหล่าอุลตร้าแมน เมื่อคุณจัดสรรความรับผิดชอบของเหล่าอุลตร้าแมนอย่างดีที่สุด

หมายเหตุ

          30% ของชุดทดสอบทั้งหมด n < 10
            50% ของชุดทดสอบทั้งหมด n < 100
           
100% ของชุดทดสอบทั้งหมด n < 1000


โจทย์โดย : สรวิทย์  สุริยกาญจน์ ( PS.int ) และแนวคิดจากค่าย สสวท. ค่ายที่ 2 ระยะ 2 ประจำปี 2553

ที่มา : ศูนย์ สอวน. โรงเรียนมหิดลวิทยานุสรณ์

ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
10 2
366 409
248 374
485 127
745 944
313 261
362 115
370 55
546 876
341 474
748 293
96725
10 5
712 420
413 638
854 53
152 430
430 703
248 450
758 388
653 578
2 302
637 198
38884


ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

กำลังออนไลน์: 19 ผู้เยี่ยมชมและ 0 สมาชิก (6 บอท)