فربد طول و عرض جغرافیایی خانه‌اش را می‌داند. فربد به متراژ رفته و طول و عرض جغرافیایی املاک همسایگانش را هم می‌بیند. به فربد کمک کنید تا بتواند برمبنای طول و عرض جغرافیایی خانهٔ خود و همسایگانش فاصلهٔ خانهٔ خود با هر کدام از آن‌ها را برحسب کیلومتر حساب کند.
عددی که به عنوان عرض جغرافیایی یا Latitudes بیان می‌شود عددی در بازهٔ ۰ تا ۹۰ و عددی که به عنوان طول جغرافیایی یا Longitudes بیان می‌شود عددی در بازهٔ ۰ تا ۱۸۰ است. در این سوال از امکان اعشاری بودن این اعداد صرف نظر کنید.
برای محاسبهٔ فاصلهٔ دو نقطه از کرهٔ زمین برحسب طول و عرض جغرافیایی از الگوریتم **haversine** استفاده کنید.
```
a = sin²(Δφ/2) + cos φ1 ⋅ cos φ2 ⋅ sin²(Δλ/2)
c = 2 ⋅ atan2( √a, √(1−a) )
d = R ⋅ c
```
در فرمول بالا φ برابر عرض جغرافیایی یا Latitudes و λ برابر طول جغرافیایی یا Longitudes هست.
پیاده‌سازی این الگوریتم در پایتون برای یک مثال خاص به این شکل خواهد بود:
```python
from math import sin, cos, sqrt, atan2, radians
# approximate radius of earth in km
R = 6373.0
# example lat and long
lat1 = radians(52.2296756)
lon1 = radians(21.0122287)
lat2 = radians(52.406374)
lon2 = radians(16.9251681)
dlon = lon2 - lon1
dlat = lat2 - lat1
a = sin(dlat / 2)**2 + cos(lat1) * cos(lat2) * sin(dlon / 2)**2
c = 2 * atan2(sqrt(a), sqrt(1 - a))
distance = R * c
```
# ورودی
در خط اول ورودی طول و عرض جغرافیایی خانهٔ فربد را بگیرید. این دو عدد با یک فاصله از هم جدا شده.
در خط سوم عدد n به معنی تعداد املاک موجود را از کاربر بگیرید.
در n خط بعد در هر خط، اطلاعات یک ملک را از کاربر بگیرید.
اطلاعات هر ملک شامل شمارهٔ id خانه، طول جغرافیایی ملک، عرض جغرافیایی ملک و مساحت ملک است.
# خروجی
خروجی برنامه باید در n خط چاپ شود.
در هر خط از خروجی شمارهٔ id خانه و فاصله خانهٔ فربد با آن خانه که با یک فاصله از هم جدا شدند چاپ شود. دقت کنید که ترتیب چاپ شدن فاصله‌ها در هر خط به **همان ترتیبی باشد که کاربر به برنامه ورودی** داده‌است یعنی **لازم نیست** برحسب id خانه‌ها مرتب شود. همچنین اعدادی که در خروجی چاپ می‌کنید با دو رقم اعشار باشد و گرد شده باشد.
# مثال
## ورودی نمونه ۱
```
170 20
6
3 160 85 40
1 175 25 70
4 160 86 40
2 176 25 100
5 169 21 400
6 40 10 300
```
## خروجی نمونه ۱
```
3 7238.69
1 756.99
4 7348.11
2 830.09
5 152.4
6 13611.73
```
محاسبهٔ فاصلهٔ خانه فربد با خانهٔ همسایگانش
فربد با جستجو در متراژ اطلاعات معاملات ملکی انجام شده شامل شمارهٔ id ملک خریداری شده، قیمت معاملهٔ انجام شده، طول جغرافیایی، عرض جغرافیایی، مساحت ملک و زمان انجام معامله را به دست می‌آورد. برنامه‌ای بنویسید که به فربد کمک کند که با در اختیار داشتن این اطلاعات بفهمد **اولین بار در چه زمانی** همهٔ ملک‌هایی که در شعاع مشخصی از خانهٔ خودش هست حداقل یک‌بار به فروش رفته‌اند. برای سادگی زمان انجام معامله را برابر یک عدد صحیح بزرگتر یا مساوی صفر فرض کنید. مقدار فاصله یک خانه از خانهٔ فربد باید **کوچکتر یا مساوی** شعاع مورد نظر باشد تا جزو خانه‌هایی باشد که می‌خواهیم بدانیم در چه زمان برای اولین بار به فروش رفته‌اند.
# ورودی
در خط اول ورودی طول و عرض جغرافیایی خانهٔ فربد را بگیرید. این دو عدد با یک فاصله از هم جدا شده.
در خط دوم مقدار شعاعی که می‌خواهیم از خانهٔ فربد بررسی کنیم را به کیلومتر بگیرید.
در خط سوم عدد n به معنی تعداد املاک موجود را از کاربر بگیرید.
در n خط بعد در هر خط، اطلاعات یک ملک را از کاربر بگیرید.
اطلاعات هر ملک شامل شمارهٔ id خانه، طول جغرافیایی ملک، عرض جغرافیایی ملک و مساحت ملک است.
در خط بعد عدد m به معنی تعداد معاملات انجام شده را از کاربر بگیرید.
در m خط بعد در هر خط، اطلاعات یک معامله را از کاربر بگیرید.
اطلاعات هر معامله شامل شمارهٔ id خانه معامله شده، مبلغ معامله و زمان انجام معامله است که هر کدام با یک فاصله از هم جدا شده‌اند.
# خروجی
خروجی برنامه باید شامل یک خط باشد.
در این خط اولین زمانی چاپ می‌شود که همهٔ ملک‌ها در شعاع مشخص شده در ورودی نسبت به خانهٔ فربد به فروش رفته‌اند. اگر **در هیچ زمانی** همهٔ ملک‌های مشخص شده در آن شعاع به فروش نرفتند **عدد -1** را در خروجی برنامه چاپ کنید.
# مثال
## ورودی نمونه ۱
```
170 20
10000
6
3 160 85 4
1 175 25 70
4 160 86 40
2 176 25 100
5 169 21 400
6 40 10 300
9
3 200000000 0
1 300000000 1
4 210000000 2
2 240000000 2
4 210000000 3
3 190000000 4
6 100000000 5
5 200000000 5
6 500000000 6
```
## خروجی نمونه ۱
```
5
```
## ورودی نمونه ۲
```
170 20
7000
6
3 160 85 4
1 175 25 70
4 160 86 40
2 176 25 100
5 169 21 400
6 40 10 300
8
3 200000000 0
1 300000000 1
4 210000000 2
2 240000000 2
4 210000000 3
3 190000000 4
6 100000000 5
6 500000000 6
```
## خروجی نمونه ۲
```
-1
```
# نکات نیازمند توجه
برای آشنایی با معنی طول و عرض جغرافیایی و محاسبهٔ فاصله برحسب کیلومتر برمبنای آن‌ها صورت پرسش اول را مطالعه کنید.
اولین زمان فروش خانه‌های اطراف فربد
فربد سوال قبل پول لازم دارد و می‌خواهد خانهٔ خود را در متراژ بفروشد ولی حدود قیمت منطقه‌اش را نمی‌داند. شما می‌خواهید با نوشتن برنامه به فربد کمک کنید تا قیمت خانه‌اش را مشخص کند. فربد با جستجوی منطقهٔ خانهٔ خود در متراژ فهرست معاملات انجام شده در آن منطقه را می‌بیند.
با داشتن فهرست معاملات انجام شده، طول و عرض جغرافیایی خانهٔ فربد و محاسبهٔ **میانگین وزنی قیمت املاک معامله شده با فاصلهٔ هر ملک معامله شده با خانهٔ فربد** قیمت مناسب برای معاملهٔ خانهٔ فربد را به ایشان پیشنهاد کنید. از تاثیر زمان انجام هر معامله در تخمین قیمت در این سوال صرف‌نظر کنید.
میانگین وزنی (Weighted mean) از فرمول زیر به دست می‌آید:
در فرمول بالا وزن‌ها (ω) برابر معکوس فاصلهٔ هر خانه تا خانهٔ فربد و اعداد (x) برابر قیمت‌ها است.
# ورودی
در خط اول ورودی طول و عرض جغرافیایی خانهٔ فربد را بگیرید. این دو عدد با یک فاصله از هم جدا شده.
در خط دوم عدد n به معنی تعداد املاک موجود را از کاربر بگیرید.
در n خط بعد در هر خط، اطلاعات یک ملک را از کاربر بگیرید.
اطلاعات هر ملک شامل شمارهٔ id خانه، طول جغرافیایی ملک، عرض جغرافیایی ملک و مساحت ملک است.
در خط بعد عدد m به معنی تعداد معاملات انجام شده را از کاربر بگیرید.
در m خط بعد در هر خط، اطلاعات یک معامله را از کاربر بگیرید.
اطلاعات هر معامله شامل شمارهٔ id خانه معامله شده، مبلغ معامله و زمان انجام معامله است که هر کدام با یک فاصله از هم جدا شده‌اند.
# خروجی
خروجی برنامه باید شامل یک خط باشد. خروجی برنامه قیمت تخمین زده شده پیشنهادی برای فروش خانهٔ فربد است.
# مثال
## ورودی نمونه ۱
```
170 20
6
3 160 85 4
1 175 25 70
4 160 86 40
2 176 25 100
5 169 21 400
6 40 10 300
9
3 200000000 0
1 300000000 1
4 210000000 2
2 240000000 2
4 210000000 3
3 190000000 4
6 100000000 5
5 200000000 5
6 500000000 6
```
## خروجی نمونه ۱
```
220068424
```
# نکات نیازمند توجه
برای آشنایی با معنی طول و عرض جغرافیایی و محاسبهٔ فاصله برحسب کیلومتر برمبنای آن‌ها صورت پرسش اول را مطالعه کنید.
مقدار فاصله به دست آمده با روش معرفی شده در سوال اول را گرد نکنید و محاسبات را تا انتها انجام دهید و در نهایت میانگین وزن‌دار به دست آمده در آخر را با حذف ارقام اعشارش چاپ کنید. (به عبارت دیگر به پایین گرد کنید.)
توجه کنید که در داده‌های معاملات انجام شده ممکن است یک خانه چند بار معامله شده باشد و شما باید مبلغ همهٔ معاملات مربوط به آن خانه را در معکوس فاصلهٔ آن خانه تا فربد حساب کنید.
فربد سؤال قبل، از فروش خانه‌اش پشیمان شده و می‌خواهد خانه‌اش را با خانه‌ای دیگر که قیمت کمتری دارد معاوضه کند. فربد قیمت مناسب تخمین زده شده برای خانهٔ خود را از سؤال قبل می‌داند. به فربد کمک کنید تا بهترین خانه‌ای که می‌تواند خانه‌اش را با آن معاوضه کند پیدا کند. بهترین خانه برای فربد، خانه‌ای است که قیمت تخمینی آن کمتر از قیمت تخمین زده شده برای خانهٔ خودش باشد و بین خانه‌های مذکور، کمترین قیمت را به ازای هر متر داشته باشد. برای پیدا کردن قیمت تخمینی هر خانه از روش معرفی شده در سؤال قبل استفاده کنید. سپس حساب کنید که فربد بعد از انجام این معاوضه چه مبلغی را باید دریافت کند.
# ورودی
در خط اول ورودی طول و عرض جغرافیایی خانهٔ فربد را بگیرید. این دو عدد با یک فاصله از هم جدا شده.
در خط دوم عدد n به معنی تعداد املاک موجود را از کاربر بگیرید.
در n خط بعد در هر خط، اطلاعات یک ملک را از کاربر بگیرید.
اطلاعات هر ملک شامل شمارهٔ id خانه، طول جغرافیایی ملک، عرض جغرافیایی ملک و مساحت ملک است.
در خط بعد عدد m به معنی تعداد معاملات انجام شده را از کاربر بگیرید.
در m خط بعد در هر خط، اطلاعات یک معامله را از کاربر بگیرید.
اطلاعات هر معامله شامل شمارهٔ id خانه معامله شده، مبلغ معامله و زمان انجام معامله است که هر کدام با یک فاصله از هم جدا شده‌اند.
# خروجی
خروجی برنامه باید شامل یک خط باشد. در خروجی مبلغی که فربد بعد از معاوضهٔ خانه‌اش به دست می‌آورد چاپ شود.
# مثال
## ورودی نمونه ۱
```
170 20
6
3 160 85 4
1 175 25 70
4 160 86 40
2 176 25 100
5 169 21 400
6 40 10 300
9
3 200000000 0
1 300000000 1
4 210000000 2
2 240000000 2
4 210000000 3
3 190000000 4
6 100000000 5
5 200000000 5
6 500000000 6
```
## خروجی نمونه ۱
**کد ارسالی برای این پرسش به صورت دستی بررسی و در صورت درست بودن کلیات راه‌حل شما امتیاز کامل و در صورت ناقص بودن آن برحسب نظر مصحح امتیازی در بازهٔ ۰ تا ۱۰۰ دریافت خواهید کرد. همچنین خطاهای کامپایل را کوئرا بررسی می‌کند و در صورت وجود امتیازی دریافت نمی‌کنید.**
# نکات نیازمند توجه
برای آشنایی با معنی طول و عرض جغرافیایی و محاسبهٔ فاصله برحسب کیلومتر برمبنای آن‌ها صورت پرسش اول را مطالعه کنید.
مقدار فاصله به دست آمده با روش معرفی شده در سوال اول را گرد نکنید و محاسبات را تا انتها انجام دهید و در نهایت میانگین وزن‌دار به دست آمده در آخر را با حذف ارقام اعشارش چاپ کنید. (به عبارت دیگر به پایین گرد کنید.)
توجه کنید که در داده‌های معاملات انجام شده ممکن است یک خانه چند بار معامله شده باشد و شما باید مبلغ همهٔ معاملات مربوط به آن خانه را در معکوس فاصلهٔ آن خانه تا فربد حساب کنید.
مبلغ به دست آمده از معاوضهٔ خانه