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\) ).
निम्नलिखित N पंक्तियों में, उन रास्तों के सिरों के निर्देशांक दर्ज करें जिनके साथ लड़कियां चलती हैं (Xi1, >Yi1< /sub>) और (Xi2, Yi2 ), द्वारा i -थ पाथ वॉकिंग i-th लड़की (\(-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