Problem

5 /7


استاد وانت

Theory Click to read/hide

تقاطع

نقطه تقاطع خطوط

a1، b1، c1 - ضرایب خط اول،
a2، b2، c2 - ضرایب خط دوم،
x، y - نقطه تقاطع.

\(x = {-(c1 \cdot b2 - c2 \cdot b1) \over (a1 \cdot b2 - a2 \cdot b1)} \\ y = {-(a1 \ cdot c2 - a2 \cdot c1) \over (a1 \cdot b2 - a2 \cdot b1)} \)

ما قبلاً می دانیم که چگونه خطوط را برای تقاطع بررسی کنیم (آنها موازی نیستند)، و نقطه تقاطع آنها را پیدا کنیم.

اکنون بیایید نحوه انجام این کار را با بخش‌ها بیاموزیم. 

ابتدا، بیایید یاد بگیریم که چگونه آنها را برای تقاطع بررسی کنیم.

قطعات قطع می شوند اگر انتهای یکی در طرف مقابل دیگری باشد و بالعکس (این به راحتی توسط ضرب ضربدر بررسی می شود).  تنها موردی که این کار نمی کند - بخش ها روی یک خط مستقیم قرار می گیرند. برای ​​آن، باید به اصطلاح تقاطع را بررسی کنید. جعبه کراندار (کادر مرزی بخش) - تقاطع پیش بینی بخش ها را در X و Y بررسی کنید.

محورها.

اکنون که می دانیم چگونه قسمت ها را برای تقاطع بررسی کنیم، بیایید یاد بگیریم که چگونه نقطه (یا قطعه) تقاطع آنها را پیدا کنیم:
- اگر همدیگر را قطع نکنند، معلوم است که چنین نقطه ای وجود ندارد؛
- در غیر این صورت، ما خطوط مستقیمی را می سازیم که این بخش ها روی آنها قرار می گیرند.

اگر موازی باشند، پاره ها روی یک خط قرار می گیرند، و ما باید قطعه تقاطع را پیدا کنیم - از حداکثر مرزهای سمت چپ پاره ها تا حداقل مرزهای راست ( نقطه کمتر از نقطه دیگر است، اگر در سمت چپ باشد، در صورت برابری X-مختصات - اگر کمتر باشد).

اگر خطوط موازی نیستند، نقطه تلاقی آنها را پیدا کنید و آن را برگردانید.

Problem

ونسسلاو اخیراً یک کتاب جدید پیکاپ خوانده و اکنون می خواهد دانش خود را در پارک آزمایش کند. برای سادگی، بیایید پارک را به عنوان مجموعه ای از مسیرها تصور کنیم که بخش هایی در یک هواپیما هستند. Wenceslas قبلاً در این پارک قدم زده است و می داند کدام دختر در کدام مسیر قدم می زند. مشکل این است که Wenceslas بسیار تنبل است و فقط در یک مسیر راه می رود. و همچنین تنبل تر از آن است که بفهمد چه نوع دخترانی را می تواند در طول مسیر ملاقات کند و به همین دلیل از شما، بهترین دوستش، خواست تا در این امر دشوار به او کمک کنید.
 
ورودی
خط اول شامل مختصات انتهای مسیر است (X1، Y1) و ( X2، Y2)، که Wenceslas در طول آنها راه می رود (\(- 20 <= X1، Y1، X2، Y2 <= 20\)).
خط دوم شامل یک عدد صحیح N است - تعداد مسیرهایی که دختران در طول آنها طی می کنند (\(0 <= N <= 5\) < /span>).
در خطوط N زیر، مختصات انتهای مسیرهایی را که دختران در آن راه می روند وارد کنید (Xi1، Yi1< /sub>) و (Xi2، Yi2 )، توسط i -امین مسیر قدم زدن i-امین دختر (\(-20 <= X_{i1}، Y_ {i1}، X_{i2 }، Y_{i2} <= 20\))
 
خروجی
در خط اول شماره M را چاپ کنید - تعداد دخترانی که مسیرهای آنها با مسیر Wenceslas قطع می شود (لمس کردن مسیرها یک تقاطع محسوب می شود).
در خط دوم اعداد M را چاپ کنید - تعداد دخترانی که قهرمان ما ملاقات خواهد کرد. دختران از یک شماره گذاری می شوند!
 
نمونه‌ها
<سر> <بدن>
# ورودی خروجی
1
0 0 2 2
1
0 2 2 0
1
1