Mafia

[Thgx0312555]

กำหนด จำนวนนับ $n$ เป็นจำนวนองค์กรมาเฟีย
มีแผนที่ประเทศหนึ่งให้แทนด้วยระนาบ 2 มิติยาวไม่จำกัด

เขตอิทธิพลของมาเฟียจะมีลักษณะเป็นวงกลมในแผนที่

สำหรับ $i \in \left\{ 1,2,...,n \right\}$
ให้เขตอิทธิพลมาเฟียองค์กรที่ $i$ มีจุดศูนย์กลางที่ $(h_i,k_i)$ และรัศมี $r_i$ โดยค่าทั้งสามเป็นจำนวนเต็ม

ตำรวจคนหนึ่งต้องการเดินเป็นเส้นตรงตามแนวที่ขนานกับแกน x หรือ แกน y จงหาว่าจะเดินผ่านเขตของมาเฟียได้มากที่สุดกี่องค์กร
จงแสดงขั้นตอนวิธีการหาคำตอบ (algorithm)

[lnพwsะบุ๑sสุ๑xล่o]

ข้อความเดิมเขียนโดยคุณ Thgx0312555

กำหนด จำนวนนับ $n$ เป็นจำนวนองค์กรมาเฟีย
มีแผนที่ประเทศหนึ่งให้แทนด้วยระนาบ 2 มิติยาวไม่จำกัด

เขตอิทธิพลของมาเฟียจะมีลักษณะเป็นวงกลมในแผนที่

สำหรับ $i \in \left\{ 1,2,...,n \right\}$
ให้เขตอิทธิพลมาเฟียองค์กรที่ $i$ มีจุดศูนย์กลางที่ $(h_i,k_i)$ และรัศมี $r_i$

ตำรวจคนหนึ่งต้องการเดินเป็นเส้นตรง จงหาว่าจะเดินผ่านเขตของมาเฟียได้มากที่สุดกี่องค์กร (ตอบในรูปตัวแปรที่กำหนดให้)

เดินผ่านมาองกรณ์มากที่สุด ในกรณีที่ ทุกองกรณ์มีอาณาเขตร่วมกัน
ให้ $h_i=h_j. k_i=k_j. r_i=r_j$ ทุก i j เปนสมาชิก {1,2,....,n}
เมื่อตำรวจเดินเปนเส้นตรงผ่าน ศก วงกลมอาณาเขตของทุกองกรณ์
จำนวนองกรที่เดินผ่านมากสุดคือ n

[Thgx0312555]

กำหนด $h_i,k_i,r_i$ เป็นค่าคงที่นะครับ

ส่วนโจทย์เอาเป็นหาขั้นตอนวิธีดีกว่าครับ หาคำตอบมันคงจะไม่สวยงามแน่ๆ
ขั้นตอนวิธี ก็อนุญาตให้ไล่ไปทีละพิกัดแล้วเช็คว่าอยู่ในวงกลมหรือไม่ ประมาณนี้ครับ
เป็นโจทย์ programming แต่เหมือนจะใช้คณิตศาสตร์ช่วย ^^

[~ArT_Ty~]

ถ้าเกิดว่าเดินแนวตรงแล้วเส้นทางเป็นเส้นสัมผัสอาณาเขตมาเฟีย

จะถือว่าผ่านมั้ยครับ??

[Thgx0312555]

ผ่านครับ เดี๋ยวขอแก้ไขโจทย์เพิ่มด้วย

[BLACK-Dragon]

ผมไม่ค่อยเข้าใจโจทย์แบบนี้เลยอ่ะครับ

$(h_i,k_i)$ มันอยู่บนเส้นตรงเดียวกันได้หมดรึเปล่าครับ