Balkan2011

BOI 2011 Day 2: Trapezoid

(หน่วยความจำ 64 MB, เวลาทำงาน 0.5 sec, คะแนนเต็ม 100 คะแนน)

เมื่อพิจารณาเส้นตรงในแนวนอนสองเส้นใดๆ สี่เหลี่ยมคางหมู Ti สามารถสร้างขึ้นระหว่างเส้นทั้งสองนี้ โดยจะประกอบด้วยเส้นแนวตั้งที่เชื่อมจุดสองจุดบนเเส้นแนวนอนด้านบนและสองจุดจากเส้นด้านล่าง (ดูรูปประกอบ) เราจะตั้งชื่อจุดเหล่านี้ว่า ai, bi, ci, และ di ที่หมายถึงจุดบนซ้าย, บนขวา, ล่างซ้าย, และล่างขวา ตามลำดับ ซึ่งเป็นเป็นจุดยอดของสี่เหลี่ยมคางหมู Ti ซับเซต S ของสี่เหลี่ยมคางหมูจะเรียกว่าอิสระต่อกันเมื่อไม่มีสองสี่เหลี่ยมคางหมูใดใน S ที่ซ้อนทับกัน

หน้าที่ของคุณ