المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۷:عملی:سوال ۱۰

مثلث قائم‌الزاویه

‎$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

ابزار صفحه