Module: Geometri


Problem

5 /7


Master Pickup

Theory Click to read/hide

Persimpangan

Titik persimpangan garisan

a1, b1, c1 - pekali bagi baris pertama,
a2, b2, c2 - pekali baris kedua,
x, y - titik persimpangan.

\(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)} \)

Kami sudah tahu cara menyemak garisan untuk persilangan (ia tidak selari) dan mencari titik persilangannya.

Sekarang mari kita pelajari cara melakukan ini dengan segmen. 

Mula-mula, mari kita pelajari cara menyemaknya untuk persimpangan.

Segmen bersilang jika hujung satu berada pada sisi bertentangan dengan yang lain dan sebaliknya (ini mudah disemak oleh hasil silang).  Satu-satunya kes apabila ini tidak akan berfungsi - segmen terletak pada satu garis lurus. Untuk itu, anda perlu menyemak persimpangan yang dipanggil. kotak sempadan (kotak sempadan segmen) - semak persilangan unjuran segmen pada X dan Y.

kapak.

Sekarang kita tahu cara menyemak segmen untuk persimpangan, mari belajar cara mencari titik (atau segmen) persimpangannya:
- jika mereka tidak bersilang, maka jelas bahawa titik sedemikian tidak wujud;
- jika tidak, kami akan membina garis lurus di mana segmen ini terletak.

Jika ia selari, maka segmen terletak pada garisan yang sama, dan kita perlu mencari segmen persimpangan - daripada maksimum sempadan kiri segmen kepada minimum sempadan kanan ( titik adalah kurang daripada titik lain, jika ia berada di sebelah kiri, sekiranya terdapat kesamaan X-koordinat - jika lebih rendah).

Jika garisan tidak selari, cari titik persilangannya dan kembalikannya.

Problem

Venceslav baru-baru ini membaca buku pikap baharu dan kini dia mahu menguji pengetahuannya di taman. Untuk kesederhanaan, mari kita bayangkan taman sebagai satu set laluan, yang merupakan segmen pada pesawat. Wenceslas telah pun berjalan di taman ini, dan dia tahu gadis mana yang berjalan di laluan mana. Masalahnya ialah Wenceslas sangat malas dan hanya berjalan di satu laluan. Dan dia juga malas untuk mengetahui jenis gadis yang boleh dia temui sepanjang perjalanan, dan oleh itu dia meminta Anda, kawan baiknya, untuk membantunya dalam perkara yang sukar ini.
 
Input
Baris pertama mengandungi koordinat hujung laluan (X1, Y1) dan ( X2, Y2), di mana Wenceslas berjalan (\(- 20 <= X1, Y1, X2, Y2 <= 20\)).
Baris kedua mengandungi integer N - bilangan laluan yang dilalui oleh gadis itu (\(0 <= N <= 5\) ).
Dalam baris N berikut, masukkan koordinat hujung laluan di mana gadis itu berjalan (Xi1, Yi1< /sub>) dan (Xi2, Yi2 ), dengan i -laluan ke-berjalan i-ke-perempuan (\(-20 <= X_{i1}, Y_ {i1}, X_{i2 }, Y_{i2} <= 20\))
 
Output
Dalam baris pertama cetak nombor M - bilangan gadis yang laluannya akan bersilang dengan laluan Wenceslas (menyentuh laluan itu dianggap sebagai persimpangan).
Dalam baris kedua cetak nombor M - bilangan gadis yang wira kita akan jumpa. Gadis bernombor bermula dari satu!
 
Contoh

 

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

# Input Output
1
0 0 2 2
1
0 2 2 0
 1
1