ข้อนี้สนุกมาก



สมมติว่าเราเป็นนักเทนนิส ซึ่งจะใช้ไม้เทนนิสของเราตบแมลงวัน

โจทย์จะให้ขนาดของแมลงวัน (f)

ขนาดของไม้ (R)

ความหนาของไม้ (t)

ความหนาของเส้นเอ็น (r)

และความห่างของเส้นเอ็น (g)







โจทย์ให้หาว่า โอกาสที่ไม้เทนนิสจะตบโดนแมลงวันเป็นเท่าไหร่?

อ่านต่อ ที่นี่



โจทย์ข้อนี้ ใครมานั่งหาสูตรคำนวนพื้นที่ก็อ้วกครับ มานั่งคำนวนเส้นตัดวงกลมทีละช่อง โหดแท้

เนื่องจากโจทย์ไม่ได้ให้คำนวนละเอียดมาก ทศนิยมหกหลัก เราสามารถใช้วิธี divide and conquer ได้

หลักการคือ แบ่งไม้เป็นสี่ส่วน แล้วก็พิจารณาดูว่าในส่วนนึง มีทั้งเส้นเอ็นและขอบเทนนิสหรือเปล่า

ถ้ามี เราก็แบ่งเป็นสี่ส่วนอีก แบ่งเฉพาะช่องที่มีขอบเทนนิสไปเรื่อยๆ จนทศนิยมไม่เกินหกหลักเราก็หยุด



เริ่มเลยละกัน

let solve f R t r g =
    let Rin = R - t - f
    let start = -(r + f)
    let r = (r + f)*2.0
    let g = g - f*2.0
    let rg = r + g

วิธีที่จะทำให้คิดง่ายขึ้นคือ เอาขนาดของแมลงวันมาขยายขนาดไม้ แล้วแมลงวันจะเหลือแค่จุดเดียว



Rin คือขนาดไม้ด้านใน (หักขนาดของแมลงวันแล้ว)

start สมมติว่า 0 คือกลางไม้ start คือจุดซ้ายล่างของเส้นเอ็นกลางไม้

r คือ ขนาดของเส้นเอ็น (รวมขนาดของแมลงวันแล้ว)

g คือ ช่องว่างระหว่างเส้นเอ็น (หักขนาดของแมลงวันแล้ว)

rg คือ ความห่างระหว่างจุดศูนย์กลางของเส้นเอ็น

let calculateGap p len =
    //calculate head
    let num = floor ((p - start) / rg)
    let headBlock = start + rg*num
    let headTouch = if p - headBlock > r
                    then 0.0
                    else min (headBlock + r - p) len
    let head = min (headBlock + rg - p) len
 
    //calculate body & tail
    let body = len - head
    let bodySize = floor (body / rg)
    let tail = body - rg*bodySize
 
    //calculate gap & return
    let headGap = head - headTouch
    let bodyGap = g * bodySize
    let tailGap = max 0.0 (tail-r)
    headGap + bodyGap + tailGap

อันนี้คือสูตรหาความยาวของช่องว่าง

p คือจุดเริ่มต้น


len คือความยาวของเส้น

concept ในการหาจะมี head, body, tail

head คือ gap ระหว่างขอบจุดเริ่มต้น ไปแต่ขอบเอ็นเส้นแรก

body คือ ขนาดของ gap ระหว่างเส้นเอ็น ภายในเส้นตรง

tail คือ gap ระหว่างขอบเอ็นเส้นสุดท้าย กับจุดสิ้นสุดของเส้นตรง

let touchString (x1,y1) (x2,y2) =
    let len = x2 - x1
    let gapH = calculateGap x1 len
    let gapV = calculateGap y1 len
    let untouch = (gapH * gapV) / (len * len)
    1.0 - untouch

function นี้ใช้คู่กับ function calculateGap

คือหาพื้นที่ของ gap หารด้วยพื้นที่ของสี่เหลี่ยม

ผลลัพธ์คือ โอกาสที่แมลงวันจะหลุดไปใน gap

let rinMixRate = (r / rg) * 0.5 + 0.5
let getHitRate p1 p2 =
    let a = center <-> p1
    let b = center <-> p2
    if b > R then
        if a > R 
        then (0.0, 0.0), false 
        else (1.0, 0.5), true
    elif b > Rin then
        if a > Rin
        then (1.0, 1.0), false
        else (rinMixRate, 1.0), true
    else
        (touchString p1 p2, 1.0), false

ถัดมาคือการคำนวน ที่รวมขอบไม้

rinMixRate คือ โอกาสคร่าวๆ ที่แมลงวันจะรอดระหว่างขอบไม้กับเส้นเอ็นได้

p1 p2 คือจุดของสี่เหลี่ยม โดย p1 คือจุดซ้ายล่าง p2 คือ ขวาบน

a กับ b คือ ระยะระหว่าง จุดศูนย์กลางถึง p1 และ p2

operator (<->) คือการหาระยะ อ่านของเก่าดูครับ



function นี้ return โอกาสที่ตีโดนแมลงวัน โอกาสที่อยู่ในไม้ และ สามารถแบ่งออกได้อีกหรือไม่

logic คือ ถ้าทั้ง p1 และ p2 อยู่นอกขอบไม้ โอกาสตีโดนคือ 0 โอกาสอยู่ในไม้คือ 0 และไม่ต้องแบ่งอีกแล้ว

ถ้า p2 อยู่นอกไม้ แต่ p1 อยู่ในไม้ โอกาสตีโดนคือ 1 โอกาสอยู่ในไม้คือ 0.5 และสามารถแบ่งเพื่อคำนวนให้ละเอียดขึ้นได้

ถ้าใน p1 และ p2 อยู่ระหว่างขอบไม้ด้านในกับด้านนอก ก็คือตีโดนแน่นอน

แต่ถ้า p2 อยู่ระหว่างขอบไม้ แต่ p1 อยู่ในวงกลม โอกาสคือ rinMixRate แต่สามารถแบ่งเพื่อคำนวนละเอียดขึ้นได้

สุดท้ายถ้า p1 และ p2 อยู่ในวงกลม ก็ใช้สูตรคำนวน touchString

let epsilon = 0.00000025 * R
 
let rec divide (x1,y1) (x2,y2) =
    let xHalf = (x1 + x2) / 2.0
    let yHalf = (y1 + y2) / 2.0
    let pos1,area1 = conquer (x1,y1) (xHalf,yHalf)
    let pos2,area2 = conquer (x1,yHalf) (xHalf,y2)
    let pos3,area3 = conquer (xHalf,y1) (x2,yHalf)
    let pos4,area4 = conquer (xHalf,yHalf) (x2,y2)
    let area = area1 + area2 + area3 + area4
    if area = 0.0
    then 0.0, 0.0
    else let pos = pos1*area1 + pos2*area2 + pos3*area3 + pos4*area4
         pos/area, area/4.0
 
and conquer (x1,y1) (x2,y2) =
    let hitRate,mix = getHitRate (x1,y1) (x2,y2)
    if mix && x2-x1 > epsilon
    then divide (x1,y1) (x2,y2)
    else hitRate

function สุดท้ายละ

epsilon คือ ขนาดที่เล็กที่สุดที่เราจะไม่คำนวนต่อ

divide คือ แบ่งสี่เหลี่ยมเป็นพื้นที่สี่ส่วนย่อย แล้วก็ conquer

ส่วน conquer คือ คำนวนหา hitRate ถ้าสามารถคำนวนละเอียดขึ้นได้ ก็ divide ไปเรื่อยๆ



ด้านบนมีใช้ keyword "and" ใน f# คือ mutually recursive function ครับ



แล้วก็ print ผลลัพธ์

let pop,_ = if g <= 0.0
            then 1.0, 1.0
            else conquer center (R,R)
sprintf "%.6f" pop

จบ