Problem

5 /7


سيد بيك اب

Theory Click to read/hide

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

a 1 ، b 1 ، c 1 - معاملات السطر الأول ،
a 2 ، b 2 ، c 2 - معاملات السطر الثاني
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)} \)

نحن نعلم بالفعل كيفية التحقق من خطوط التقاطع (فهي ليست متوازية) ، وإيجاد نقطة تقاطعها.

الآن دعنا نتعلم كيفية القيام بذلك باستخدام المقاطع .

أولاً ، دعنا نتعلم كيفية فحصها بحثًا عن التقاطع.

تتقاطع المقاطع إذا كانت نهايات أحدهما على جانبي الآخر والعكس صحيح (يمكن التحقق من ذلك بسهولة بواسطة المنتج المتقاطع). & nbsp ؛ الحالة الوحيدة عندما لا يعمل ذلك - الأجزاء تقع على خط مستقيم واحد. & nbsp ؛ لذلك ، تحتاج إلى التحقق من تقاطع ما يسمى. المربع المحيط (المربع المحيط بالمقطع) - تحقق من تقاطع إسقاط المقاطع على X و Y . محاور

الآن بعد أن عرفنا كيفية فحص المقاطع بحثًا عن التقاطع ، دعنا نتعلم كيفية العثور على نقطة (أو مقطع) تقاطعهم:
- إذا لم يتقاطعوا ، فمن الواضح أن هذه النقطة غير موجودة ؛
- وإلا فإننا نبني خطوطًا مستقيمة تقع عليها هذه القطاعات.

إذا كانتا متوازية ، فإن المقاطع تقع على نفس الخط ، ونحتاج إلى إيجاد مقطع التقاطع - من الحد الأقصى للحدود اليسرى للمقاطع إلى الحد الأدنى من الحدود اليمنى ( النقطة أقل من النقطة الأخرى ، إذا كانت إلى اليسار ، في حالة المساواة X - الإحداثيات - إذا كانت أقل). إذا لم تكن الخطوط متوازية ، فابحث عن نقطة تقاطعها وأعدها.

Problem

قرأ Venceslav مؤخرًا كتابًا صغيرًا جديدًا ويريد الآن اختبار معرفته في الحديقة. للتبسيط ، دعنا نتخيل الحديقة كمجموعة من المسارات ، وهي أجزاء على مستوى. لقد سار Wenceslas بالفعل في هذه الحديقة ، وهو يعرف الفتاة التي تمشي على طول أي طريق. المشكلة هي أن Wenceslas كسول للغاية ويمشي فقط على طول مسار واحد. وهو أيضًا كسول جدًا لمعرفة أي نوع من الفتيات يمكن أن يلتقي به على طول الطريق ، ولذلك طلب منك ، أفضل صديق له ، مساعدته في هذا الأمر الصعب.
& nbsp؛
إدخال
يحتوي السطر الأول على إحداثيات نهايات المسار ( X 1 ، Y 1 ) و ( X 2 ، Y 2 ) ، التي يسير فيها وينسيسلاس ( \ (- 20 & lt؛ = X1، Y1، X2، Y2 & lt؛ = 20 \) ).
يحتوي السطر الثاني على عدد صحيح N - عدد المسارات التي تسير الفتيات على طولها ( \ (0 & lt؛ = N & lt؛ = 5 \) ).
في سطور N التالية ، أدخل إحداثيات نهايات المسارات التي تسير الفتيات على طولها ( X i1 ، Y i1 ) و ( X i2 ، Y i2 ) ، عن طريق i - مسار المشي i -th girl ( \ (- 20 & lt؛ = X_ {i1} ، Y_ {i1}، X_ {i2}، Y_ {i2} & lt؛ = 20 \) )
& nbsp؛
الإخراج
في السطر الأول اطبع الرقم M - عدد الفتيات اللاتي ستتقاطع مساراتهن مع مسار Wenceslas (يعتبر لمس المسارات تقاطعًا).
في السطر الثاني ، اطبع أرقام M - أعداد الفتيات التي سيلتقي بها بطلنا. يتم ترقيم البنات ابتداء من واحد! نبسب ؛
أمثلة <الجسم>
# إدخال الإخراج
1
0 0 2 2
1
0 2 2 0
1
1

نبسب ؛