Yo`nalishlar
Hozirda online

Statistika

Masalalar soni: 909

Foydalanuvchilar soni: 8825

Jo'natishlar soni: 714634

Muhokama yozuvlari: 4541

Yangiliklar soni: 98

Yangiliklar izohlari: 1179


So'ngi izohlar

381. Shrek
Vaqt limiti: 1 sekund
Xotira limiti: 64 MB

Shrek dehqonchilikni yaxshi koradi. U yaqinda umr yoldoshi Fiona, mushuk va eshak bilan birgalikda oziga yangi bir yerni ozlashtirib, bog qilmoqchi boldi. Dastlab Shrek bogning arxitektura rejasini tuzib chiqdi. Bu rejaga asosan, bog N tomonli kopburchak korinishida boladi va uning uchlari (x1,y1), (x2,y2),, (xN,yN) nuqtalarda yotadi. Shrek oz bogi chegarasini |(x1,y1), (x2,y2)| ga kesma tortib, |(x2,y2), (x3,y3)| ga kesma tortib(va hokazo) belgilab oldi. Shrek oz ishiga puxta bolganligi sababli bog tevaragini mustahkam orab olmoqchi. Buning uchun u, bogning arxitekturadagi rejasini koordinatalar sistemasiga qoyganda, bogning chegaralaridan butun sonly nuqtalarga tosiq qoyadi va bog cheti boylab tor tortmoqchi. Lekin bog maydoni katta bolganligi sababli Shrek ham, eshak ham, mushuk ham, Fiona ham nechta tosiq kerakligini hisoblab chiqa olishmadi. Siz ularga yordam beradigan shunday dastur tuzingki, bog chetlaridagi butun sonly nuqtalar soni(nechta tosiq kerakligi) hisoblansin.

shrek_01

Kiruvchi malumotlar: Birinchi satrda N natural soni (0 ≤ N 106). Keyingi har bir N ta satrda ikkitadan son xi,yi sonlari, bog rejasidagi shaklning uchlari koordinatalari. Bog tomonlarining ixtiyoriy ikkitasi bir togri chiziqda yotmasligi kafolatlanadi.

Chiquvchi malumotlar: Bitta butun son bog qurilishida kerak boladigan tosiqlar soni.

Kiruvchi malumotlar

Chiquvchi malumotlar

1

3

0 0

1 1

1 0

3

 

 

 

2

5

1 0

1 3

5 5              

5 1

3 2

12

 

 

Tayyorladi: Yo'ldoshboy Sultonov
Mening urinishlarim(0) Muhokama (1) Jo'natish Eng yaxshi yechimlar Barcha muvaffaqiyatli urinishlar(66) Barcha urinishlar(145)