1164 : ระเบิดมหาประลัย (Bomb)
Problem type : Batch
Time limit : 2.0 second(s)
Memory limit : 32 megabyte(s)

ทหาร นาวิกโยธินกำลังต้องการที่จะบุกเข้าไปชิงตัวประกันออกมาจากสถานที่ลับแห่ง หนึ่ง ในการที่จะบุกเข้าไปในที่แห่งนี้ ทหารนาวิกโยธินจะต้องผ่านเหมืองระเบิด โดยในเหมืองระเบิดนี้จะมีทั้งระเบิดจริงและระเบิดปลอมอยู่ทั้งหมดจำนวน n ตำแหน่งที่ไม่ซ้ำกัน คือ {p1,p2,p3,…,pn} โดยที่ pi = (xi,yi) เป็น พิกัดของระเบิด หน่วยข่าวกรองของทหารทราบมาว่า ระเบิดจริงจะอยู่ในตำแหน่งที่มีลักษณะพิเศษที่เรียกว่าตำแหน่งมหันตภัย ซึ่งลักษณะพิเศษดังกล่าวถูกระบุตามเงื่อนไขดังต่อไปนี้

1.       - ศัพท์ทางการทหารกล่าวว่าตำแหน่ง p1 บดบังตำแหน่ง p2 ก็ต่อเมื่อ x1 > x2 และ y1 > y2

2.       - ตำแหน่งมหันตภัยคือ ตำแหน่งที่ไม่มีตำแหน่งอื่นๆ บดบัง

จงเขียนโปรแกรมที่มีประสิทธิภาพในการระบุตำแหน่งมหันตภัยที่มีระเบิดจริงทั้งหมด

ข้อมูลนำเข้า

1.       บรรทัดแรกเป็นค่าของตัวแปร n โดยที่ 1 ≤ n ≤ 1,000,000

2.       บรรทัดที่สองถึง n+1 ระบุตำแหน่งของระเบิดทั้งหมด แต่ละบรรทัดระบุค่าของตำแหน่งเป็นจำนวนเต็มบวกสองตัว x และ y โดยมีช่องว่างคั่นอยู่ระหว่างตัวเลขทั้งสอง โดยที่ 1 ≤ x, y ≤ 10,000,000

ข้อมูลส่งออก

ให้ระบุตำแหน่งมหันตภัยทั้งหมด โดยให้แต่ละบรรทัดระบุค่าของตำแหน่งเป็นจำนวนเต็มบวกสองตัว x และ y โดยมีช่องว่างคั่นอยู่ การเรียงก่อนหลังของตำแหน่งให้จากค่าพิกัด x จากน้อยไปมาก หากพิกัดคู่ใดมีค่าพิกัด x เท่ากัน ให้เรียงตามพิกัด y จากมากไปน้อย

หมายเหตุ แนะนำให้ใช้ scanf ในการรับค่าและ printf ในการแสดงผล


ที่มา : การแข่งขันคอมพิวเตอร์โอลิมปิกระดับชาติครั้งที่ 7 (NUTOI7) :: ดัดแปลงเล็กน้อย
ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
5
9 1
8 2
7 3
6 4
5 5
5 5
6 4
7 3
8 2
9 1
7
1 2
2 4
4 1
7 3
5 5
6 6
3 7
3 7
6 6
7 3

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

กำลังออนไลน์: 13 ผู้เยี่ยมชมและ 4 สมาชิก (0 บอท)