المپدیا

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

ابزار کاربر

ابزار سایت


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

PolyDis

یک $n$ نقطه‌ای یک مجموعه‌ی $n$ تایی از نقاط مانند $P=\{p_1,p_2,…,p_n\}$ است که در آن $p_i$ ها نقاطی از صفحه هستند. فاصله‌ی دو $n$ نقطه‌ای $P=\{p_1,p_2,…,p_n\}$ و $Q=\{q_1,q_2,…,q_n\}$ عبارت است از طول بردار میانگین بردارهای واصل نقاط $P$ و $Q$ یا به عبارت دیگر طول بردار $\frac{1}{n^2} \sum_{i=1}^n \sum_{j=1}^n \overrightarrow{p_i q_j}$.

$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

ابزار صفحه