สมมติว่า มีรูปหลายเหลี่ยมที่มีจุดยอด n จุด แกนพลิก n จุด และจุดหมุน n จุด สิ่งต่อไปนี้เป็นจริงสำหรับแกนพลิกและจุดหมุน
- ถ้า n เป็นเลขคี่ แกนที่พลิกแต่ละแกนจะผ่านจุดยอดเพียงจุดเดียวและอยู่ตรงกลางของด้านตรงข้าม
- ถ้า n เป็นเลขคู่ ครึ่งหนึ่งของแกนผ่านจุดยอดตรงข้ามคู่หนึ่ง และอีกครึ่งหนึ่งผ่านคู่ของด้านตรงข้าม
- แกนสองอันที่ตามมามีมุม 360/2n
ตอนนี้ เราหมุนรูปหลายเหลี่ยมที่ให้มา เรามีโรเตเตอร์ n ประเภทที่แตกต่างกัน k-rotator หมุนรูปหลายเหลี่ยมที่แกน k ตามเข็มนาฬิกา (360 x k)/n องศา มีรายการอินพุตรายการที่มีจำนวนเต็มหลายคู่ จำนวนเต็มแรกของคู่แสดงว่ารูปหลายเหลี่ยมถูกพลิกกลับหรือหมุน ถ้าจำนวนเต็มแรกคือ 1 รูปหลายเหลี่ยมจะหมุน ถ้าเป็น 2 รูปหลายเหลี่ยมจะพลิก จำนวนเต็มที่สองคือ k หากพลิกรูปหลายเหลี่ยม ก็จะพลิกที่แกน k หรืออย่างอื่น หากหมุนก็จะถูกหมุนด้วยมุม 360/2n การหมุนและการพลิกจะเสร็จสิ้นในขณะที่รายการไม่ว่างเปล่า
งานของเราคือการเพิ่มองค์ประกอบอื่นในรายการเพื่อให้สามารถรีเซ็ตรูปหลายเหลี่ยมไปยังตำแหน่งเริ่มต้นได้
รูปภาพระบุแกนหมุนของรูปหลายเหลี่ยมสองประเภท
ดังนั้น หากอินพุตเป็น n =6, input_list =[[1, 2], [1, 4], [2, 3], [2, 5], [1, 6]] ผลลัพธ์จะเป็น (1, 4)
หลังจากการแปลง การหมุนตามแกนที่ 4 จะรีเซ็ตรูปหลายเหลี่ยมเป็นตำแหน่งเริ่มต้น
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- decision_var :=เท็จ
- ตำแหน่ง :=0
- สำหรับแต่ละรายการใน input_list ให้ทำ
- x :=item[0]
- y :=item[1]
- ถ้า x เท่ากับ 1 แล้ว
- ตำแหน่ง :=ตำแหน่ง + y
- อย่างอื่น
- ตำแหน่ง :=y - ตำแหน่ง
- decision_var :=not(decision_var)
- ตำแหน่ง :=ตำแหน่ง mod n
- ถ้าคำตัดสิน_varไม่ใช่ศูนย์ แล้ว
- คืนคู่ (2, ตำแหน่ง)
- มิฉะนั้น
- คืนคู่ (1, n - ตำแหน่ง)
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def solve(n, input_list): decision_var = False position = 0 for item in input_list: x = item[0] y = item[1] if x == 1: position += y else: position = y - position decision_var = not decision_var position = position % n if decision_var: return (2, position) else: return (1, n - position) print(solve(6, [[1, 2], [1, 4], [2, 3], [2, 5], [1, 6]]))
อินพุต
6, [[1, 2], [1, 4], [2, 3], [2, 5], [1, 6]]
ผลลัพธ์
(1, 4)
