+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- هم اکنون دیجیکالا می‌خواهد برای سرویس دهی به $n$ شهر، تعدادی دفتر در نقاط مختلف تاسیس کند. پس از این تاسیس‌ها، باید تعدادی سیستم ارسال بسته بین شهرها و دفترها تعریف شود. هر سیستم ارسال بسته می‌تواند از یک شهر یا دفتر شروع شده و در یک شهر یا دفتر به اتمام برسد. می‌توان شهرها را بصورت نقاطی داخل صفحه مختصات دکارتی در نظر گرفت که شهر $i$ در مختصات $(x_i, y_i)$ قرار دارد. تاسیس هر دفتر هزینه‌ی $D$ دارد و تعریف هر سیستم ارسال بسته به اندازه‌ی فاصله‌ی ابتدا و انتهای سیستم، هزینه خواهد داشت. هدف این است که با داشتن محل شهرها و مقدار $D$، روشی بهینه برای تاسیس دفترها و تعریف سیستم‌های ارسال بسته ارائه شود که: 1. بتوان به هر شهر از یک دفتر بسته ارسال کرد؛ یعنی هر شهر بوسیله‌ی سیستم‌های ارسال بسته بصورت مستقیم یا غیر مستقیم به حداقل یک دفتر مسیر داشته باشد. بصورت مستقیم یعنی یک سیستم ارسال بسته از این شهر به یک دفتر وجود داشته باشد و غیر مستقیم یعنی بتوان با دنباله‌ای از سیستم‌های ارسال بسته، بسته را از این شهر پس از گذراندن از تعدادی شهر دیگر به یک دفتر رساند. 2. میزان هزینه‌ی کلی کمینه شود. برای مثال همیشه می‌توان با تاسیس $n$ دفتر که هریک در یکی از شهر‌ها قرار دارد، با هزینه‌ی برابر $n \times D$ به هدف گفته‌شده رسید. همچنین می‌توان با یافتن مرکز ثقل همه‌ی شهرها و تاسیس یک دفتر در آنجا، با هزینه‌ی برابر $D$ + (مجموع فاصله‌ی شهرها از مرکز ثقل) به هدف گفته‌شده رسید؛ اما معمولا هیچیک از این دو راه‌حل گفته‌شده کم‌خرج ترین راه‌حل نیستند! در این سوال تعدادی تست وجود دارد که مختصات شهرها در آن برگرفته از مختصات تعدادی شهر در دنیای‌ واقعی است. برنامه‌ی شما هرچه با هزینه‌ی کمتری بتواند به هدف گفته شده برسد، امتیاز بیشتری کسب خواهد نمود. در هر تستی که به برنامه‌ی شما داده می‌شود، مقدار پیش بینی شده برای هزینه یا $expected$ همراه نقشه به شما داده می‌شود و اگر شما بتوانید با هزینه‌ی کمتر یا مساوی $expected$ به هدف گفته شده برسید، نمره‌ی آن تست را دریافت می‌کنید. **توجه کنید که راهکار شما لازم نیست بهترین راهکار باشد؛ کافیست از مقدار پیش بینی‌شده بهتر باشد تا خروجی شما درست در نظر گرفته شود.** ۱۰ نقشه در تست‌ها وجود دارد که هریک ۳ بار آمده است که مقدار‌ $expected$ در آن‌ها متفاوت است. تعداد ارسال‌های شما در این سوال تاثیری روی رتبه‌ی شما ندارد. # ورودی در سطر اول ورودی سه عدد طبیعی $n$ و $D$ و $expected$ آمده‌است. عدد $n$ نمایانگر تعداد شهر‌های داخل نقشه است، عدد $D$ نمایانگر هزینه‌ی تاسیس هر دفتر است و عدد $expected$ برابر هزینه‌ی پیش بینی شده برای پروژه است. سپس در $n$ سطر بعدی مختصات $n$ شهر در نقشه آمده‌است. مختصات شهر $i$ بصورت $x_i\ y_i$ آمده‌است که: $$-1000 \le x_i, y_i \le 1000$$ $$1 \le n \le 100$$ # خروجی در سطر اول خروجی دو عدد $k$ و $m$ چاپ کنید که به ترتیب نمایانگر تعداد دفاتری که می‌خواهید تاسیس کنید و تعداد سیستم‌های ارسال بسته هستند. سپس در هریک از $k$ سطر بعدی مختصات یک دفتر را بصورت $x\ y$ خروجی دهید. سپس در هریک از $m$ سطر بعدی دو مختصات خروجی دهید که نمایانگر دو سر یک سیستم ارسال بسته در نقشه‌ی مالی ارائه شده‌ی شما هستند. **امکان تاسیس یک دفتر روی مختصات شهرها وجود دارد؛ در این حالت نیازی به خروجی دادن سیستم ارسال بسته بین دفتر و شهر هم مختصات نیست.** # مثال ## ورودی نمونه ۱ ``` 4 10 40 1 0 0 1 -1 0 0 -1 ``` ## خروجی نمونه ۱ ``` 4 0 1 0 0 1 -1 0 0 -1 ``` هزینه‌ی ساخت نقشه‌ی خروجی این نمونه برابر ۴۰ است. ## ورودی نمونه ۲ ``` 4 10 15 1 0 0 1 -1 0 0 -1 ``` ## خروجی نمونه ۲ ``` 1 4 0 0 0 0 1 0 0 0 0 1 0 0 -1 0 0 0 0 -1 ``` هزینه‌ی ساخت نقشه‌ی خروجی این نمونه برابر ۱۴ است.

حل سؤال در بانک سؤالات