ПЪРВО КОНТРОЛНОза разширения национ

ПЪРВО КОНТРОЛНО
за разширения национален отбор
Хасково, 9 май 2011 г.
група A
Задача A2. ПА-ПА-ПА-ПАЛАТКА!
Автор: Момчил Томов
След осемчасовия поход, инж. Тошко и компания най-накрая стигнаха до
хижата. Хвърлиха багажа, пиха по една студена вода и се захванаха с разпъването на
палатката (нали не си помислихте, че ще плащат за нощувки в хижата?). Тошко намери
идеалното място – една голяма поляна точно до хижата – но тъкмо да разпъне
палатката и се натъкна на едно голямо кравешко изпражнение. Разбира се, не може да
разпъне палатката върху него – няма да е комфортно, а и ще я измърси. Затова се
премести малко настрани, но не щеш ли – там още едно. Оказа се, че цялата поляна е
осеяна с изпражнения. Сега Тошко е изправен пред сериозен инженерен проблем – има
ли място на поляната, където да разпъне палатката, без да застъпва някое кравешко
изпражнение?
За целите на задачата, поляната може да се представи като правоъгълник с
размери W на H, с долен ляв ъгъл в точката с координати (0, 0) и горен десен в (W, H).
Изпражненията са представени като точки с целочислени координати в този
правоъгълник. Палатката е квадрат със страна S и може да се разпъне само върху
квадратен регион със страна S, за който е изпълнено следното:
1. Намира се във вътрешността на поляната
2. Не съдържа изпражнения във вътрешността си (може да съдържа по контура)
3. Страните му са успоредни на координатните оси (Тошко много държи входът на
палатката да е насочен на изток, така че сутрин козирката да го пази от
слънцето)
Напишете програма tetetent, която съобщава дали съществува място, където
може да се разпъне палатката.
Вход
На първия ред от стандартния вход ще се намират целите числа W, H и S (1 < W,
1 < H, 1 ≤ S ≤ min(W, H)) – съответно дължината и височината на поляната, и страната
на палатката. На следващия ред ще се намира числото N (1 < N) – броят кравешки
изпражнения. На i-тия от следващите N реда ще се намира двойката цели числа Xi и Yi
(0 ≤ Xi ≤ W, 0 ≤ Yi ≤ H) – координатите на следващото изпражнение. Никои две точки
няма да съвпадат.
Изход
На единствения ред от стандартния изход изведете YES или NO, съответно ако
има или няма квадратен регион, който да отговаря на гореописаните условия.
Оценяване
Оценяването ще се извърши с четири различни групи от тестове, наричани
подзадачи, подобно на 22-рата Международна Олимпиада по Информатика. За да
получите точки за дадена подзадача, решението Ви трябва да дава верен отговор на
всички тестове с посочените в подзадачата ограничения.
Подзадача #1 – 25 точки
W, H ≤ 100, N ≤ 200
Подзадача #2 – 25 точки
W, H ≤ 1000, N ≤ 200 000
Подзадача #3 – 25 точки
W, H ≤ 109
, N ≤ 2000
Подзадача #4 – 25 точки
W, H ≤ 109
, N ≤ 200 000
Примери
Вход 1 Долният ляв
ъгъл на
палатката
може да е във
всяка от
точките (1, 2),
(2, 1), (2, 2),
(2, 3) и (3, 1)
Вход 2 Единственото
изпражнение е
по средата на
поляната и
пречи на всяко
възможно
разположение
на палатката
Вход 3 Винаги
може да
сложим
палатка
със страна
1
7 6 3
6
1 3
2 2
4 1
2 5
5 4
6 2
4 6 4
1
2 3
2 2 1
9
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
Изход 1 Изход 2 Изход 3
YES NO YES

Kết quả (Việt) 2:

PRVO KONTROLNO
của giãn phế quản là lựa chọn của dân tộc
Haskovo, 09 Tháng 5 2011
grupa A
A2 nhiệm vụ. ! Pa-pa-pa-TENT
Tác giả: Momchil Tomov
Tiếp osemchasoviya đi lang thang, Ing. Toshko và công ty Nye xà cừ stignaha để
hizhata. Hvrliha hành lý tại nước Piha Edna Studena kìa zahvanaha với razpvaneto trên
palatkata (Nali không pomislihte B, Th shte plaschat cho noschuvki trong hizhata?). Toshko dự
idealnoto vị trí - Edna Golyama thanh toán bù trừ chính xác hizhata - nhưng có tkmo razpne
palatkata kìa natkna trên edno Goliamo kraveshko izprazhnenie. Giải cấu trúc kìa, không quá Mauger
razpne palatkata vrhu anh - có Nyama e thoải mái, và tôi shte izmrsi. Satow se
premesti Malko nastrani nhưng không schesh có - có osche edno. Nó bật se, lĩnh vực che tsyalata E
Osei với izprazhneniya. Sega Toshko e izpraven trước khi vấn đề Engineer seriozen - Ima
cho dù vị trí trên polyanata, kdeto có razpne palatkata không có zastpva nyakoe
kraveshko? Izprazhnenie
Đối Celite trên zadachata, polyanata Mauger yes se đại diện Kato pravoglnik với
kích thước W trên H, với Dolen lyav gl trong tochkata có tọa độ (0, 0) và Goren nướu (W, H).
Izprazhneniyata sa predstaveni Kato điểm với tọa độ nguyên trong Tosi
pravoglnik. Palatkata e ss nước vuông S và Mauger yes se razpne vrhu chính
là khu vực hình vuông của ss nước S, Coit của e izplneno slednoto:
1. Namir se câu vtreshnostta trên polyanata
2. Không sdrzha izprazhneniya câu vtreshnostta si (có sdrzha Mauger trên mạch)
3. Nước mu sa usporedni trên trục tọa độ (Toshko nhiều vhodt drzhi trên
palatkata vâng e nasochen trên Iztok, chẳng hạn Th sutrin kozirkata có của Pasi từ
slntseto)
ghi Programa tetetent, koyato sobschava đã sschestvuva vị trí, kdeto
Mauger yes se razpne palatkata.
Đăng
Trong prviya ed từ đầu vào chuẩn shte se namirat Celite số W, H và S (1 <W,
1 <H, 1 ≤ S ≤ min (W, H)) - sotvetno dlzhinata và visochinata trên polyanata và thôn quê
trên palatkata. Trên sledvaschiya ed shte Nầy Namir chisloto N (1 <N) - broyat kraveshki
izprazhneniya. Trên i-ment của sledvaschite N Reda shte Nầy Namir dvoykata mục đích của Xi và Yi
(0 ≤ Xi ≤ W, 0 ≤ Yi ≤ H) - tọa độ trên sledvaschoto izprazhnenie. Niko hai điểm
Nyama có svpadat.
Izhodya
trên ed duy nhất từ chuẩn izhodya izvedet YES hoặc NO, sotvetno ako
ima hoặc Nyama là khu vực vuông Coit có otgovarya về điều kiện goreopisanite.
Otsenyavane
Otsenyavaneto shte se izvrshi với chetiri hướng tới nhóm khác nhau của kiểm tra, narichani
nhiệm vụ nhỏ như 22 Rath International Olympic tin học. Cho nên
nhận được điểm cho dadena subtask, reshenieto Wee tryabva Yeah, chúng ta hãy can ngăn đúng để
vsichki thử nghiệm với posochenite trong những hạn chế podzadachata.
Subtask # 1-25 điểm
W, H ≤ 100, N ≤ 200
subtask # 2-25 điểm
W, H ≤ 1000 , N ≤ 200 000
Sub-Task # 3-25 điểm
W, H ≤
109, N ≤ 2000
subtask # 4-25 điểm
W, H ≤
109, N ≤ 200 000
Ví dụ
Input 1 Dolni lyav
gl trên
palatkata
Mauger vâng e vv
tất cả các loại
điểm (1, 2),
(2, 1), (2, 2),
(2, 3) và (3, 1)
Input 2 Edinstvenoto
izprazhnenie e
của sredata trên
polyanata và
Precu trên khác nhau
Cố
vấn tiêu dùng
tại palatkata
Login 3 Vinagi
Mauger có
thêm các
lều
ss nước
1
7 6 3
6
1 3
2 2
4 1
2 5
5 4
6 2
4 6 4
1
2 3
2 2 1
9
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
izhodya izhodya 1 2 3 izhodya
YES NO YES