Courses

Algoritma

Kaedah scanline

Module: Kaedah scanline

Problem

1 /4

Perlindungan minimum

Theory Click to read/hide

Problem

Satu set segmen tertentu dengan koordinat integer hujung \([L_i, R_i]\) diberikan pada baris. Antara set yang diberikan, pilih subset segmen yang merangkumi sepenuhnya segmen \([0, M]\), (M — nombor asli) yang mengandungi bilangan segmen terkecil.

Input

Baris pertama mengandungi M pemalar (\(1<=M<=5000\)). Setiap baris berikutnya mengandungi sepasang nombor L_i dan R_i (\(|L_i|,|R_i| < 50000\)), yang menentukan koordinat hujung kiri dan kanan segmen. Senarai itu berakhir dengan sepasang sifar. Jumlah bilangan segmen tidak melebihi 100,000.

Output

Dalam baris pertama fail output cetak bilangan minimum segmen yang diperlukan untuk meliputi segmen \([0; M]\). Seterusnya, keluarkan senarai subset penutup, diisih dalam tertib menaik mengikut koordinat hujung kiri segmen. Senarai segmen adalah output dalam format yang sama seperti dalam input. Dua sifar di belakang tidak diperlukan. Jika segmen \([0; M]\) ialah set asal segmen \([L_i, R_i] \)< /span> tidak mungkin, satu frasa “Tiada penyelesaian” harus dikeluarkan.