DWITE '10 R1 #4 - Planting Trees

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 64M

Problem type
DWITE Online Computer Programming Contest, October 2010, Problem 4

You are considering planting trees around your house, but there are only a few good sites to do so. Furthermore, it would be best if the planted trees surrounded the house — that is, the house is within the area formed between all the trees.

The input will contain 5 test cases, an integer 3 \le N \le 30, followed by N lines of integer X\ Y pairs, -1000 \le X, Y \le 1000, describing possible plant locations. Consider the house to be a single point at location 0,0.

The output will contain 5 lines, an integer number of possible valid configurations for exactly 3 trees.

Notes: the order in which the trees are planted does not matter. The house must be strictly contained within the area; that is, if the house is exactly on the line between two trees, then this configuration does not count.

Sample Input

4
0 1
-1 -1
0 -1
1 -1
6
-1 1
0 1
1 1
-1 -1
0 -1
1 -1

Sample Output

1
2

Problem Resource: DWITE

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments

There are no comments at the moment.