المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:سوال های ای سی ام سایت تهران:دوره ی ۷:f

Fortune at El Dorado

کامران در سفرش به ال‌دورادو ثروت زیادی به‌دست آورد. پس از آن‌که به پادشاه در حل یک مسئله‌ی سخت ریاضی کمک کرد، پادشاه به او بخشی از باغ سلطنتی را هدیه داد. پادشاه نامه‌ای به باغبان نوشت که یک قسمت مستطیل شکل از باغ سلطنتی با یک مساحت مشخص به کامران داده شود. حتما می‌توانید حدس بزنید که درخت‌های ال‌دورادو از طلا هستند.

پس از آن‌که کامران نامه را به باغبان سلطنتی داد،‌ کامران فهمید که متاسفانه هیچ الگویی برای مکان‌های درختان در باغ وجود ندارد. کامران برای کسب سود بیشینه، با باغبان صحبت کرد و او را متقاعد کرد که خیلی مهم نیست اگر کامران مکان سهمش از باغ را خودش تعیین کند و یا مساحت کم‌تری از آن‌چه در نامه آمده انتخاب کند. هرچند باغبان اصرار کرد که باغ کامران باید مستطیلی با اضلاع موازی با اضلاع باغ(که خود یک مستطیل است) بوده و رئوسش روی نقاط صحیح قرار گرفته باشند. همچنین مساحت این مستطیل باید مثبت باشد تا پادشاه به چیزی شک نکند.

حال با دانستن مکان درختان و بیش‌ترین مساحت ممکن برای باغ کامران(مقدار نوشته شده در نامه‌ی پادشاه)،‌کامران باید مستطیلی که در شرایط باغبان صدق کرده و تعداد درختان درون آن بیشینه باشد را پیدا کند. اگر درختی روی محیط این مستطیل باشد کامران می‌تواند آن درخت را متعلق به خودش در نظر بگیرد.

ورودی

در خط اول ورودی عدد $T$ آمده‌است که تعداد سناریوهای مختلف را نشان می‌دهد. برای هر سناریو چند خط مختلف آمده است. در خط اول هر سناریو عدد $(1 \le F \le 1000)F$،‌تعداد درختان درون باغ و عدد $A$، مساحت باغ کامران در نامه‌ی پادشاه، آمده‌است. هر یک از $F$ خط بعدی مکان یک درخت را نشان می‌دهند که در هر یک از آن‌ها دو عدد $x$ و $y(1 \le x, y \le 1000)$ آمده‌اند. هیچ دو درختی در یک نقطه قرار ندارند.

خروجی

به ازای هر سناریو یک عدد خروجی دهید که برابر با بیش‌ترین تعداد درختی است که کامران می‌تواند در باغ خود داشته باشد.

محدودیت‌ها

  • محدودیت زمان: ۱۰ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
1
3 3
1 1
1 3
1 5
2

پاسخ

منتظر پر کردن این قسمت توسط علاقمندان هستیم.


ابزار صفحه