hint

Á÷»ç°¢ÇüÀÇ °¡·Î±æÀ̸¦ w ¶ó°í Çϸé, ¼¼·Î±æÀÌ h´Â l/2 - w ·Î Á¤ÇØÁø´Ù.

±×¸®°í ÁÂÇ¥ÀÇ ¹üÀ§´Â ÃÖ´ë 10,000±îÁö ³ª¿Ã ¼ö ÀÖÁö¸¸, ½ÇÁ¦·Î ÀԷ¹޴ ¹°°í±âÀÇ À§Ä¡´Â 100°³À̹ǷÎ, ¿ì¸®¿¡°Ô ÀÇ¹Ì ÀÖ´Â ÁÂÇ¥°¡ x, y ÃÖ´ë 100°³À̹ǷΠÀԷ¹ÞÀº ÁÂÇ¥µé¿¡ ´ëÇؼ­¸¸ °í·ÁÇÏ¸é µÈ´Ù.

µû¶ó¼­ Á÷»ç°¢ÇüÀÇ °¡·Î±æÀÌ¿Í ¼¼·Î±æÀ̸¦ Á¤ÇÑ ÈÄ, ÀÔ·Â ¹ÞÀº ÁÂÇ¥ x, yµé¿¡ ´ëÇؼ­¸¸ plane sweepÀ» ÇÏ¸ç °¢ ÁöÁ¡µéÀ» ±âÁ¡À¸·Î ±×¹°À» ÆîÃĺ¸¾Æ, ¸ðµç °í±âµé¿¡ ´ëÇØ ±×¹° ¾È¿¡ µé¾î¿À´ÂÁö¸¦ È®ÀÎÇÑ´Ù.

ÀÌ ¹æ¹ýÀ» ¾²¸é O(LM^3)ÀÇ ½Ã°£¿¡ Çظ¦ ãÀ» ¼ö ÀÖÀ¸¸ç, ÀÌ·¸°Ô Ç® °æ¿ì ¸¸Á¡À» ¹Þµµ·Ï test case°¡ ±¸¼ºµÇ¾î ÀÖ´Ù.

   

[ȨÀ¸·Î]  [µÚ ·Î]