Mafia
กำหนด จำนวนนับ $n$ เป็นจำนวนองค์กรมาเฟีย
มีแผนที่ประเทศหนึ่งให้แทนด้วยระนาบ 2 มิติยาวไม่จำกัด เขตอิทธิพลของมาเฟียจะมีลักษณะเป็นวงกลมในแผนที่ สำหรับ $i \in \left\{ 1,2,...,n \right\}$ ให้เขตอิทธิพลมาเฟียองค์กรที่ $i$ มีจุดศูนย์กลางที่ $(h_i,k_i)$ และรัศมี $r_i$ โดยค่าทั้งสามเป็นจำนวนเต็ม ตำรวจคนหนึ่งต้องการเดินเป็นเส้นตรงตามแนวที่ขนานกับแกน x หรือ แกน y จงหาว่าจะเดินผ่านเขตของมาเฟียได้มากที่สุดกี่องค์กร จงแสดงขั้นตอนวิธีการหาคำตอบ (algorithm) |
อ้างอิง:
ให้ $h_i=h_j. k_i=k_j. r_i=r_j$ ทุก i j เปนสมาชิก {1,2,....,n} เมื่อตำรวจเดินเปนเส้นตรงผ่าน ศก วงกลมอาณาเขตของทุกองกรณ์ จำนวนองกรที่เดินผ่านมากสุดคือ n |
กำหนด $h_i,k_i,r_i$ เป็นค่าคงที่นะครับ
ส่วนโจทย์เอาเป็นหาขั้นตอนวิธีดีกว่าครับ หาคำตอบมันคงจะไม่สวยงามแน่ๆ ขั้นตอนวิธี ก็อนุญาตให้ไล่ไปทีละพิกัดแล้วเช็คว่าอยู่ในวงกลมหรือไม่ ประมาณนี้ครับ เป็นโจทย์ programming แต่เหมือนจะใช้คณิตศาสตร์ช่วย ^^ :laugh: |
ถ้าเกิดว่าเดินแนวตรงแล้วเส้นทางเป็นเส้นสัมผัสอาณาเขตมาเฟีย
จะถือว่าผ่านมั้ยครับ?? |
ผ่านครับ เดี๋ยวขอแก้ไขโจทย์เพิ่มด้วย
|
ผมไม่ค่อยเข้าใจโจทย์แบบนี้เลยอ่ะครับ
$(h_i,k_i)$ มันอยู่บนเส้นตรงเดียวกันได้หมดรึเปล่าครับ |
เวลาที่แสดงทั้งหมด เป็นเวลาที่ประเทศไทย (GMT +7) ขณะนี้เป็นเวลา 19:10 |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Modified by Jetsada Karnpracha