سوال ۲۰

در یک کشور، $n$‌ شهر داریم. مختصات هر شهر یک $(x,y)$ است که $0 \leq x,y \leq 10^4$ و $x$ و $y$ اعداد صحیح هستند. می‌خواهیم در $m$ شهر آنتن نصب کنیم به طوری که مجموع فاصله‌ی هر شهر تا نزدیک‌ترین آنتن، کمینه شود. برنامه‌ای بنویسید که این مقدار کمینه را به‌دست آورد و شهرهایی را که باید در آن‌ها آنتن نصب شود، مشخص کند.

در سطراول فایل ورودی، اعداد $n$ و $m$ نوشته شده‌اند.

سپس در $n$ سطر، در هر سطر، مختصات یک شهر داده شده است.

در سطر اول فایل خروجی، تا دقت سه رقم اعشار، مقدار کمینه را بنویسید.

در $m$ سطر بعد، در هر سطر شماره‌ی یک شهر که باید در آن آنتن نصب شود را بنویسید. شهرها را با شروع از ۱ شماره‌گذاری می‌کنیم.

توجه

$n$ حداکثر ۱۰۰۰ می‌باشد.

هر تست که به برنامه‌ی شما داده می‌شود ۱۰ نمره دارد. برنامه‌ی ما، یک جواب $A$ پیدا می‌کند و فرض کنیم که جواب برنامه‌ی شما $B$ است. اگر جواب شما غلط باشد، نمره صفر می‌شود. در غیر این صورت، اگر $B \leq A$ نمره ۱۰ است. اگر $A \times 1.1< B$ نمره صفر است. اگر $A \times 1.05 < B \leq A \times 1.1$ نمره ۱ می‌شود. اگر $A \times 1.025 < B \leq A \times 1.1$ نمره ۲ می‌شود. و به همین ترتیب تا ۹.

سه مثال ورودی و جواب برنامه‌ی ما (پس از ۱۵ ثانیه) در اختیار شما قرار داده می‌شود. توجه کنید که در خروجی‌های ما فقط عدد داده شده است، ولی برنامه‌ی باید شهرهایی که آنتن در آن‌ها نصب می‌شوند را مشخص کند.