시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 19 | 12 | 12 | 63.158% |
In the Regional Park of the Haute Vallée de Chevreuse, N observation houses have been built, for the purpose of watching and counting local animals. Furthermore, to help animals and tourists move more efficiently, paths were built along the axes of a grid: these paths are all along the straight vertical (i.e., along a North–South axis) and horizontal (i.e., along an West–East axis) lines.
Every house has a wide observation window that is oriented towards the South. This window allows people to see in every direction that is within a 60◦ angle with the South – thereby covering a third of the plane – which offers a beautiful show in the spring and summer seasons. However, during winter, the animals stay home or migrate to warmer countries, and the trees have lost their leaves and become so thin that they are barely visible, so the only things that people can see and count are the other observation houses.
Yet, this is still a fun excursion in the wild for the days after SWERC. A group of N students have decided to go to the Regional Park. You are helping them with the planning, having the coordinates of every house. Each student is going to one of the houses.
Once arrived, each participant plans to stand at the observation window of her own house, and to take a picture of every other house she can see from that spot. After the excursion, you will have to gather all the pictures that the students have taken.
Given the list of coordinates of the observation houses, how many pictures will you gather?
The input consists of the following lines:
Your output should contain a single line with a single integer equal to the total number of pictures that will be taken.
6 2 3 4 3 1 1 0 0 3 2 4 1
11
The map corresponding to this example is depicted on the right. From the house A, you can see the entire gray area, and thus the participant who chose to go to house A will take 4 pictures.
If a house Y lies on the border of the third of plane visible from another house X, the participant who went to house X will not take a picture of Y, as this picture would only be partial. If a house Z lies on the segment [X,Y] when Y is visible from X, then the participant who went to house X will take one picture focusing only on the house Y, and another picture focusing only on the house Z.
ICPC > Regionals > Europe > Southwestern European Regional Contest > SWERC 2019 PC번