You are not allowed to perform this action
مثلث قائمالزاویه
$n$ نقطه با مختصات صحیح در صفحهی مختصات دوبعدی داده شدهاند. میخواهیم
- اوّلاً: تعداد مثلثهای قائمالزاویهای که رئوسش $3$ تا از این نقاط باشد و اضلاع زاویه قائمهاش موازی محورهای مختصات (افقی، عمودی) باشد را بشماریم (فرضاً $M$ مثلّثِ $T_1$ تا $T_M$).
- ثانیاً: تعداد زوج مثلثهای $(T_i, T_j)$ از این $M$ مثلث را بشماریم که $T_i$ با $T_j$ متشابه (از ریاضیات دوم راهنمایی میدانیم دو مثلث متشابهاند اگر بتوان یکی را با چرخش، قرینهکردن و تغییر اندازه (بهیک نسبت میان اضلاع) به دیگری تبدیل کرد) باشد. تعداد این زوجها (دقّت کنید که $(T_i, T_j)$ با $(T_j, T_i)$ یکی بوده و تنها یک بار شمارده میشوند) را نیز $K$ مینامیم.
برنامهای بنویسید که با دریافت مختصات $n$ نقطه، $M$ و $K$ را محاسبه کند.
ورودی
- در سطر اول ورودی $n$ (تعداد نقاط) میآید.
- در $n$ سطر بعدی، در هر سطر ابتدا مؤلفهی $x$ و سپس مؤلفهی $y$ یک نقطه میآید.
- $1 \le n \le 5,000$
- مختصات نقاط صحیح بوده و در بازهی $[0, 5000]$ قرار دارند.
- هیچ دو نقطهای روی هم قرار نگرفتهاند.
- اعداد خروجی در تایپ
intجا میشوند. - در صورتی که تنها عدد $M$ را درست چاپ کنید، $30$ درصد نمره را خواهید گرفت. برای گرفتن این $30$ درصد، لازمست دقیقاً $2$ عدد در خروجی بنویسید که عدد اوّل $M$ محسوب خواهد شد.
خروجی
- در سطر اول خروجی $M$ (تعداد مثلثهای مطلوب) را بنویسید.
- در سطر دوم $K$ (تعداد زوج مثلثهای متشابه) را بنویسید.
محدودیتها
- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
ورودی و خروجی نمونه
| ورودی نمونه | خروجی نمونه |
|---|---|
| 6 4 3 2 5 0 3 2 3 2 7 2 1 | 6 7 |