Sunčanje
레이팅 미적용의견: 0
4 \(s / 256\) \(MB / 130\) points
Little Slavko dreamed of an unusual dream. One sunny morning, \(N\) white rectangles climbed one by
one on the rectangular roof of Slavko's house. They were preparing for an exotic trip to Hawaii -
sunbathing. Each rectangle chose a place on the roof and lay in such a way that its sides were
parallel to the edges of the roof. It is possible that some rectangles overlapped parts of other
rectangles that have previously lain down on Slavko's roof. For each rectangle its length \(A\) {i}{ }, height \(B\) _{i}
and distances from the left and bottom edges of the roof, \(X\) {i}{ } and \(Y\) {i}{ }, respectively, are known.
After sunset, rectangles climbed down the roof and went to sleep dreaming of beautiful Hawaii
beaches and their bodies tanned to yellow due to the sun exposure. However, the next morning they
spotted a problem! Only parts of rectangles that had been directly exposed to the sun became yellow.
In other words, if parts of a rectangle were covered by some other rectangle, then those parts didn't
change colour from white to yellow.
Sadly, rectangles that did not change the colour entirely were forced to cancel the trip.
Write a program that will determine for each rectangle if it is going to Hawaii or not.
In test cases worth 10% of total points, it will hold that \(N\) ≤ 10 000.
4 \(s / 256\) \(MB / 130\) points
The first line contains a positive integer \(N\) (1 ≤ \(N\) ≤ 100 000), number of rectangles.
Each of the next \(N\) lines contains four integers \(X\) {i}{ }, \(Y\) {i} (0 ≤ \(X\) { }, \(Y\) ≤10 {9}{ }), \(A\) {i} and \(B\) (1 ≤ \(A\) {i}{ }, \(B\) _{i} ≤10 {9}{ }),
describing rectangles in the order they were climbing and lying down on the roof. \(X\) _{i} represents
distance from the left edge of the roof, \(Y\) {i} the distance from the bottom edge of the roof, \(A\) the length
and \(B\) {i}{ } the height of the i {th}{ } rectangle.
You have to print \(N\) lines. In i {th}{ } line print “DA” (Croatian for yes, without quotation marks) if i ^{th}
rectangle will go to Hawaii, otherwise print “NE” (Croatian for no).
5
1 1 4 2
6 1 1 1
2 2 2 3
3 4 3 2
4 0 1 2
3
3 3 1 1
2 2 3 3
1 1 5 5output
NE
DA
NE
DA
DA
NE
NE
DAClarification of the first sample:
The first and the third rectangle are not entirely exposed to the sun, meaning they won’t change colour entirely
and won’t go to Hawaii. Other rectangles are exposed to the sun entirely.
평가 및 의견
Sunčanje
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Sunčanje