Processing math: 42%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی انتخاب تیم:دوره ی ۱۶:سوال ۱۱

PolyDis

یک n نقطه‌ای یک مجموعه‌ی n تایی از نقاط مانند P={p1,p2,,pn} است که در آن pi ها نقاطی از صفحه هستند. فاصله‌ی دو n نقطه‌ای P={p1,p2,,pn} و Q={q1,q2,,qn} عبارت است از طول بردار میانگین بردارهای واصل نقاط P و Q یا به عبارت دیگر طول بردار 1n2ni=1nj=1piqj.

k تا n ﻧﻘﻄﻪﺍﯼ ﺑﻪ ﻣﺎ ﺩﺍﺩﻩ ﺷﺪﻩ ﺍﺳﺖ ﻭ ﺍﺯ ﻣﺎ ﺧﻮﺍﺳﺘﻪﺍﻧﺪ m تا دورترین جفت از n نقطه‌ای‌ها را بیابیم. به عبارت دیگر، اگر تمام \binom{k}{2} ﺗ‰ﺎ ﻓ‰ﺎﺻ‰ﻠ‰ﻪﯼ n تایی‌ها را در نظر بگیریم، m تا بزرگ‌ترین مقدار را می‌خواهیم.

ورودی

در سطر نخست ورودی سه عدد صحیح k،n و m به ترتیب نوشته شده‌اند(1\leq n \leq 10000 و 1\leq k \leq 100 و 1\leq m \leq min\{10^6, \binom{k}{2}\}). در k سطر بعدی در هر سطر n نقطه‌ی یک n نقطه‌ای آمده است. دقت کنید که هر نقطه از دو مولفه‌ی x و y ساخته شده است و در نتیجه در هر سطر 2n عدد آمده است.(تمام مختصات عدد صحیح هستند و قدر مطلق‌شان از ۱۰۰ بیش‌تر نیست.)

خروجی

در m سطر جداگانه از خروجی، m عدد اعشاری با دقیقا ۴ رقم اعشار (به صورت گرد شده) بنویسید که نشان‌دهنده‌ی فاصله‌ی m دورترین زوج n نقطه‌ای‌ها می‌باشند. این m فاصله باید به ترتیب از بزرگ به کوچک نوشته شوند.

محدودیت‌ها

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

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

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

ابزار صفحه