บนระนาบสองมิติมีกรอบสี่เหลี่ยมหลากสีวางอยู่ เอาแผ่นกระดาษสี่เหลี่ยมอีกหนึ่ง แผ่นวางลงไปต้องการทราบว่ากระดาษนั้น ทับกับพื้นที่ภายในกรอบสี่เหลี่ยมทั้ง หมดกี่กรอบ การระบุตำแหน่งของกรอบสี่เหลี่ยมและกระดาษทำโดยระบุพิกัดของจุดมุมบนซ้ายและจุดมุมล่างขวา กระดาษจะทับกับกรอบสี่เหลี่ยมถ้าพื้นที่ในระนาบร่วมระหว่างพื้นที่ในกรอบกับกระดาษมีมากกว่า 0 (นั่นคือถ้าพบกันที่จุดมุมหรือแค่ที่ขอบจะไม่ถือว่าเป็นการทับกัน)
ยกตัวอย่างเช่น ถ้ามีกรอบสี่เหลี่ยม 3 กรอบดังรูปด้านล่างซ้าย สี่เหลี่ยมทั้ง สามสามารถระบุตำแหน่งได้เป็น (1,8)-(5,1), (2,6)-(9,2) และ (6,7)-(9,3) ถ้ามีวางกระดาษลงไปยังตำแหน่ง (0,3)-(6,0) หรือที่ตำแหน่ง (2,9)-(7,6) จะทับกับกรอบสี่เหลี่ยม 2 รูป ถ้าวางกระดาษที่ตำแหน่ง (3,5)-(8,4) จะทับกับกรอบสี่เหลี่ยม 3 รูป
แม้ว่าจะมีกระดาษวางลงไปหลายแผ่น ให้พิจารณาว่าการวางกระดาษแต่ละแผ่นไม่เกี่ยวข้องกัน
งานของคุณ
เขียนโปรแกรมรับข้อมูลตำแหน่งของกรอบสี่เหลี่ยม จากนั้น รับตำแหน่งของกระดาษที่วางลงไปแต่ละแผ่น
แล้วคำนวณว่ากระดาษแต่ละแผ่นนั้น ทับกับกรอบสี่เหลี่ยมกี่กรอบ
ข้อมูลนำเข้า
บรรทัดแรก ระบุจำนวนเต็มสองจำนวน N และ M (1 ≤ N ≤ 1,000; 1 ≤ M ≤ 1,000)
จากนั้น อีก N บรรทัด ระบุตำแหน่งของกรอบสี่เหลี่ยมแต่ละกรอบ กล่าวคือในบรรทัดที่ 1 + i สำหรับ 1 ≤ i ≤ N จะระบุจำนวนเต็มสี่จำนวน X1i Y1i X2i Y2i (แต่ละจำนวนมีค่าระหว่าง -30,000 ถึง 30,000; X1i < X2i ; Y1i > Y2i) เพื่อระบุว่ากรอบสี่เหลี่ยมที่ i มีจุดมุมบนซ้ายที่ตำแหน่ง (X1i, Y1i) จุดมุมล่างขวาที่ตำแหน่ง (X2i, Y2i)
อีก M บรรทัด ระบุข้อมูลของกระดาษแต่ละแผนที่วางลงไป กล่าวคือ ในบรรทัดที่ 1 + N + j
สำหรับ 1 ≤ j ≤ M จะระบุจำนวนเต็มสี่จำนวน A1j B1j A2j B2j (แต่ละจำนวนมีค่าระหว่าง -30,000 ถึง
30,000; A1j < A2j ; B1j > B2j) เพื่อระบุว่ากระดาษแผ่นที่ j เมื่อวางลงในระนาบแล้ว มีจุดมุมบนซ้ายที่
ตำแหน่ง (A1j, B1j) จุดมุมล่างขวาที่ตำแหน่ง (A2j, B2j)
ข้อมูลส่งออก
มีทั้ง สิ้น M บรรทัด บรรทัดที่ j สำหรับ 1 ≤ j ≤ M ระบุจำนวนกรอบสี่เหลี่ยมที่ทับกับกระดาษแผ่นที่ j
ที่มา: การแข่งขัน YTOPC กุมภาพันธ์ 2552
ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
3 3 1 8 5 1 2 6 9 2 6 7 9 3 0 3 6 0 2 9 7 6 3 5 8 4 | 2 2 3 |