สมมติว่าเรามีรายการของจุดที่เรียงลำดับแทนจุดสิ้นสุดรูปหลายเหลี่ยมอย่างง่ายบนระนาบ 2 มิติ เราต้องหาปริมณฑลของรูปหลายเหลี่ยมนี้
ดังนั้น หากอินพุตเหมือนกับคะแนน =[(0, 0), (0,5), (3, 5), (3,0)] ผลลัพธ์จะเป็น 16 เพราะ
สองด้านยาว 3 และสองด้านยาว 5 ดังนั้น 2*5 + 2*3 =16
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดฟังก์ชัน getInfo() นี่จะใช้เวลา x1, y1, x2, y2
- คืนค่ารากที่สองของ ((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)) ซึ่งเป็นระยะทางแบบยุคลิด
- ระหว่าง (x1, y1) และ (x2, y2)
- จากวิธีหลัก ให้ทำดังนี้
- N :=ขนาดของจุด
- (firstx, firsty) :=คะแนน[0]
- (prevx, prevy) :=(firstx, firsty)
- res :=0
- สำหรับผมอยู่ในช่วง 1 ถึง N-1 ทำ
- (nextx, nexty) :=คะแนน[i]
- res :=res + getInfo(prevx, prevy, nextx, nexty)
- prevx :=nextx
- prevy :=nexty
- res :=res + getInfo(prevx, prevy, firstx, firsty)
- ผลตอบแทน
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
from math import sqrt def getInfo(x1, y1, x2, y2): return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)) def solve(points): N = len(points) firstx, firsty = points[0] prevx, prevy = firstx, firsty res = 0 for i in range(1, N): nextx, nexty = points[i] res = res + getInfo(prevx,prevy,nextx,nexty) prevx = nextx prevy = nexty res = res + getInfo(prevx,prevy,firstx,firsty) return res points = [(0, 0), (0,5), (3, 5), (3,0)] print(solve(points))
อินพุต
[(0, 0), (0,5), (3, 5), (3,0)]
ผลลัพธ์
16.0
