ปัญหา
ให้ด้านตรงข้ามมุมฉาก hypo และพื้นที่ area หาฐานและสูงของสามเหลี่ยมมุมฉาก ถ้าไม่ได้คืน False
ตัวอย่าง
hypo = 10, area = 24 → ฐาน=6, สูง=8 (6²+8²=10², ½×6×8=24) → (6, 8)
แนวคิดการแก้ปัญหา (Binary Search)
- พื้นที่สูงสุดเมื่อฐาน=สูง:
maxArea = 0.5 * (hypo/√2)² = hypo²/4 - ถ้า area > maxArea → False
- Binary search หาฐานในช่วง [0, hypo/√2] ให้พื้นที่ตรงตามที่ต้องการ
โค้ดตัวอย่าง
from math import sqrt
def area_of_triangle(base, hypo):
height = sqrt(hypo*hypo - base*base)
return 0.5 * base * height
def solve(hypo, area):
max_area = area_of_triangle(hypo / sqrt(2), hypo)
if area > max_area:
return False
left, right = 0.0, hypo / sqrt(2)
while right - left > 1e-6:
mid = (left + right) / 2
if area_of_triangle(mid, hypo) >= area:
right = mid
else:
left = mid
base = round(left)
height = round(sqrt(hypo*hypo - base*base))
return base, height
print(solve(10, 24)) # (6, 8)
อินพุต / เอาต์พุต
Input: 10, 24 Output: (6, 8)
