แสวงหาบางสิ่ง (acm15_findsome)


Time limit:
1000 ms
Memory limit:
64 MB

ณ จักรวาลแห่งจินตนาการ มีดาวเคราะห์ในจินตนาการอยู่มากมาย แต่เนื่องจากคุณเบื่อที่จะจิ้นจักรวาลของคุณตามกฎฟิสิกส์ของไอน์สไตน์แล้ว คุณจึงได้ทำการจิ้นกฎฟิสิกส์ใหม่ในจักรวาลจินตนาการของคุณ โดยคุณได้ทำการจิ้นจักรวาลในจินตนาการของคุณให้กลายเป็นแผ่นแบนราบที่มีดาวเคราะห์ ซึ่งย่อมต้องกลายเป็นจุดในจักรวาลนี้แทน โดยเมื่อคุณมองไปยังดาวเคราะห์ต่างๆ คุณรู้สึกถึงความจืดชืดของดาวเคราะห์ในจินตนาการของคุณ คุณจึงจำเป็นต้องจิ้นต่อ คุณได้ทำการจิ้นให้ ดาวเคราะห์แต่ละดวงมีคนอยู่เพียงคนเดียว โดยกำหนดให้พวกเขาเหล่านั้น เป็นคนที่ฉลาดมากและมีอายุไม่จำกัด โดยคุณอยากเห็นความเป็นไปได้ของพวกเขา คุณจึงได้ทำการปล่อยพวกเขาเหล่านั้นทิ้งไว้ในโลกจินตนาการ เพื่อให้คุณสามารถเห็นความเป็นไปได้ของพวกเขาเหล่านั้น คุณจึงได้จิ้นกฎฟิสิกส์ของเวลาในจักรวาลจินตนาการของคุณ ให้มีค่าสัมพัทธ์กับจักรวาลที่คุณอยู่ตอนนี้ โดยให้เดินเร็วกว่าล้านเท่า แปลว่า 1วันในโลกจริง จะเท่ากับ 1ล้านวันในจักรวาลนั้น โอ้ว มันช่างยอดเยี่ยม คุณพูดกับตัวเอง ก่อนจะทิ้งจักรวาลนั้นไว้ วันต่อมา คุณจึงกลับมาสังเกตจักรวาลในจินตนาการของคุณอีกครั้ง ปรากฏว่าคุณพบเห็นอะไรบางอย่าง พวกเขาเหล่านั้น พยายามติดต่อสื่อสารกัน ใช่แล้ว เพราะพวกเขามีอายุอนันต์ แต่พวกเขาไปไหนไม่ได้ เพราะเขายืนอยู่บนดาวที่เป็นจุด ซึ่งมันก็เป็นเพียงจุด อะไรมันจะน่าเศร้าขนาดนี้ แต่ด้วยความฉลาดที่คุณมอบให้พวกเขา พวกเขาได้พยายามหากฎฟิสิกส์ที่คุณลืมจิ้นเพิ่มเพื่อมาสร้างเทคโนโลยีไปยังอีกดาวหนึ่ง แต่พวกเขาไม่มีกระทั่งจุดให้สร้างยานขี่ไปอีกดาวหนิ คุณจึงสงสัยว่าพวกเขาทำอะไร แต่นั่นก็ดึกเกินไปแล้ว คุณจึงเข้านอนก่อน แล้วค่อยมาดูโลกแห่งนี้อีกครั้งในวันต่อมา

วันต่อมา คุณเห็นพวกเขาได้ทำอะไรบางอย่างกับดาวเคราะห์ที่พวกเขายืนอยู่ ดาวเหล่านั้นกำลังเคลื่อนที่เข้าหาดาวอีกดวงหนึ่ง พวกเขาให้ดาวเคราะห์เป็นยานอวกาศ!! ทีนี้คุณก็ลุ้นว่า ใครจะเป็นคู่แรกที่จะได้เจอกัน แต่คุณอยากรู้เร็วกว่ามานั่งรอ คุณจึงได้ทำการหยิบพิกัดดาวทั้งหมด N ดาวในจักรวาลจินตนาการของคุณมาใส่ในคอมพิวเตอร์ของคุณ แล้วคำนวณหาระยะทางสั้นที่สุดจากทุกคู่ดาวที่เป็นไปได้ แต่คุณรู้สึกว่าปัญหานี้มันคุ้นๆ และง่ายเกินไป คุณไม่ชอบความน่าเบื่อ คุณจึงทำการจิ้นโจทย์ใหม่อีกครั้ง โดยคุณปรับโจทย์ให้ยากขึ้นเล็กน้อย โดยคราวนี้คุณอยากรู้ระยะทาง K อันดับของระยะจากทุกคู่ดาวที่สั้นที่สุด แต่เนื่องด้วยคุณจิ้นได้แค่โจทย์ แต่คุณไม่มีความสามารถพอ ดังนั้น คุณ(ในโจทย์) จึงได้จิ้นให้คุณ(ที่อ่านข้อนี้อยู่)ทำการเขียนโปรแกรมแก้มันแทน โอ้วมันช่างง่ายเสียนี่กระไร แก้มันเลยซิ คุณๆทั้งหลาย

จงเขียนโปรแกรมเพื่อแก้ปัญหาให้คุณ(ในโจทย์)ได้รู้คำตอบของคำถามที่เขาจิ้นทิ้งไว้

Input

บรรทัดแรกประกอบด้วยจำนวนเต็ม T ซึ่ง 1 ≤ T ≤ 10 แทนจำนวนคำถาม

บรรทัดต่อมา ประกอบด้วยจำนวนเต็ม N, K แทน ดาวในจักรวาลทั้งหมด และ อันดับ

โดย 1 ≤ N ≤ 50,000 และ 1 ≤ K ≤ 4 และ K < N

บรรทัดต่อมาอีก N บรรทัด แทน คู่พิกัดจำนวนเต็ม Xi, Yi ของดาวที่ i เมื่อ 1 ≤ i ≤ N

โดย 1 ≤ Xi, Yi ≤ 1,000,000 และ รับประกันว่า จะไม่มีดาวดวงไหนอยู่จุดเดียวกัน

บรรทัดต่อมาจะกลับมาซ้ำกับรูปแบบเดิมด้านบนไปเป็นจำนวนอีก T-1 ครั้ง

Output

มีทั้งหมด T บรรทัด แต่ละบรรทัด ต้องแสดงกำลัง2ของคำตอบโดยเป็นจำนวนเต็มทั้งหมด K คำตอบจากงานที่คุณได้รับ

Editor:

Source: ACM ICPC 2015 Thailand Local Central Group B

Select description language

Thai (raw)
English (raw)

If you don't find what you want

Translate it!

Edit this description

Edit

Tag

None