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