Module: Carian ternary


Problem

4 /9


rumah tepi jalan

Problem

Kementerian Pengangkutan Jalan telah memutuskan untuk membina pejabat baharu untuk dirinya sendiri. Memandangkan menteri kerap keluar untuk meninjau laluan paling penting, maka diputuskan supaya pejabat kementerian tidak terletak terlalu jauh dari laluan tersebut.
 
Penjajaran yang paling penting ialah garis lurus pada satah. Kementerian mahu memilih lokasi untuk pejabatnya supaya jarak maksimum dari pejabat ke lebuh raya adalah sesingkat mungkin.
 
Anda perlu menulis program yang, memandangkan lokasi lebuh raya yang paling penting, menentukan lokasi optimum rumah untuk pejabat Kementerian Pengangkutan Jalan.
 
Input
Baris pertama fail input mengandungi satu integer n — bilangan jejak yang paling penting (1  ≤ n ≤ 104 ).
 
N baris seterusnya menerangkan kesan. Setiap surih diterangkan oleh empat integer x1, y1, x2 dan y2 dan adalah lurus garisan yang melalui titik (x1, y1)  dan (x2, y2) . Koordinat titik yang diberikan tidak melebihi 104 dalam nilai mutlak. Titik (x1 , y1)  dan (x2 , y2)  tidak sepadan dengan mana-mana baris.
 
Output
Fail output harus mengandungi dua nombor nyata yang dipisahkan dengan ruang: koordinat titik di mana pejabat Kementerian Pengangkutan Jalan harus dibina. Koordinat modulo tidak boleh melebihi 109, ia dijamin bahawa sekurang-kurangnya satu jawapan sedemikian wujud. Jika terdapat beberapa jawapan yang optimum, cetak mana-mana daripadanya.
 
Jawapan mesti mempunyai ralat mutlak atau relatif tidak lebih daripada 10&tolak;6, yang bermaksud yang berikut. Biarkan jarak maksimum dari titik yang dilukis ke beberapa jejak adalah sama dengan x, dan dalam jawapan yang betul ia adalah sama dengan y. Jawapan akan dikira jika nilai ungkapan | x .tolak; y | /  maks(1, |y| )  tidak melebihi 10&tolak;6.
 
 

 Olimpik Peribadi, Olimpik Seluruh Rusia untuk murid sekolah, Peringkat Serantau, 2011, hari ke-2, Masalah D 

time 1000 ms
memory 256 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
4
0 0 0 1
0 0 1 0
1 1 2 1
1 1 1 2
 0.5000000004656613 0.4999999995343387
7
376 -9811 376 -4207
6930 -3493 6930 -8337
1963 -251 1963 -5008
-1055 9990 -684 9990
3775 -348 3775 1336
7706 -2550 7706 -8412
-9589 8339 -4875 8339
 4040.9996151750674 12003.999615175067