یک شرکت مخابراتی در حال توسعه شبکه جی‌اس‌ام خود در شهر پکن می‌باشد. $n$تا از خانه‌های شهر باید توسط شبکه پوشش داده شود. بدلیل محدودیت‌های بودجه، شرکت می‌تواند تنها یک آنتن نصب کند. برای ساده کردن تعیین محل قرار دادن این آنتن، $3$ تا از این $n$ خانه انتخاب شده و آنتن در مرکز دایره‌ای که از این خانه‌ها می‌گذرد نصب می‌شود. محدوده تحت پوشش این آنتن طوری است که تمام خانه‌هایی که درون و روی مرز این دایره قرار دارند را پوشش می‌دهد. شرکت قصد دارد این $3$ خانه را به صورت تصادفی انتخاب کند، آن‌ها می‌خواهند متوسط تعداد خانه‌های تحت پوشش در تمام امکان‌های ممکن برای انتخاب محل آنتن را محاسبه کنند.

برای مثال فرض کنید $4$ خانه $A$، $B$، $C$ و $D$ وجود دارند که موقعیت‌شان در شکل زیر نشان داده شده است.

اگر ما دایره تعیین شده توسط $ABC$ یا $BCD$ را انتخاب کنیم، تمام خانه‌ها پوشش داده می‌شوند. اگر ما دایره تعیین شده توسط $ABD$ یا $ACD$ را انتخاب کنیم، خانه چهارم با این آنتن پوشش داده نمی‌شود. بنابر این متوسط تعداد خانه های تحت پوشش برابر است با $3.5 = (4 + 4 + 3 + 3)/4$

شما باید با داشتن مکان خانه‌ها، متوسط تعداد خانه‌های تحت پوشش را محاسبه کنید. موقعیت خانه‌ها به صورت اعداد صحیح در سیستم مختصات دو بعدی داده شده‌ است. تضمین شده‌است که هیچ سه خانه‌ای روی یک خط و هیچ چهار خانه‌‌‌ای روی یک دایره قرار ندارند.

• خط اول شامل یک عدد صحیح مثبت $n$ بیانگر تعداد خانه‌ها است.
• در هر یک از n خط بعدی مکان یکی از خانه‌ها مشخص شده است. برای $i \in \{1, \cdots, n\}$ مختصات خانه $i$ با زوج عدد صحیح $x_i$ و $y_i$ در خط $i+1$اُم که با یک فاصله از هم جدا شده‌اند، بیان شده است.
• در ۱۰۰ درصد از تست‌ها، برای $i \in \{1, \cdots, n\}$ مختصات خانه‌ها طوری است که $-1000000 \leq x_i,y_i \leq 1000000$ و هم‌چنین هیچ سه خانه‌ای روی یک خط و هیچ چهار خانه‌ای روی یک دایره قرار ندارند.
• در ۴۰ درصد از تست‌ها $n \leq 100$
• در ۷۰ درصد از تست‌ها $n \leq 500$
• در ۱۰۰ درصد از تست‌ها $3 \leq n \leq 1,500$

تنها سطرِ خروجی شامل یک عدد حقیقی که بیانگر متوسط تعداد خانه‌های تحت پوشش است، می‌باشد. خطای مطلق جواب باید کمتر یا مساوی $0.01$ باشد.

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

• سوال قبل