در یک کشور، n شهر داریم. مختصات هر شهر یک (x,y) است که 0≤x,y≤104 و x و y اعداد صحیح هستند. میخواهیم در m شهر آنتن نصب کنیم به طوری که مجموع فاصلهی هر شهر تا نزدیکترین آنتن، کمینه شود. برنامهای بنویسید که این مقدار کمینه را بهدست آورد و شهرهایی را که باید در آنها آنتن نصب شود، مشخص کند.
در سطراول فایل ورودی، اعداد n و m نوشته شدهاند.
سپس در n سطر، در هر سطر، مختصات یک شهر داده شده است.
در سطر اول فایل خروجی، تا دقت سه رقم اعشار، مقدار کمینه را بنویسید.
در m سطر بعد، در هر سطر شمارهی یک شهر که باید در آن آنتن نصب شود را بنویسید. شهرها را با شروع از ۱ شمارهگذاری میکنیم.
توجه
n حداکثر ۱۰۰۰ میباشد.
هر تست که به برنامهی شما داده میشود ۱۰ نمره دارد. برنامهی ما، یک جواب A پیدا میکند و فرض کنیم که جواب برنامهی شما B است. اگر جواب شما غلط باشد، نمره صفر میشود. در غیر این صورت، اگر B≤A نمره ۱۰ است. اگر A×1.1<B نمره صفر است. اگر A×1.05<B≤A×1.1 نمره ۱ میشود. اگر A×1.025<B≤A×1.1 نمره ۲ میشود. و به همین ترتیب تا ۹.