There are N trees in a plantation. Each tree is assigned an information card which notes the following information: location (x, y), type (coffee or tea).
The plantation manager wants to construct a fence around the plantation. For minimum cost, the fence length needs to be as short as possible.
The manager also wants to build a watering system based on tubes to let water runs from the pump to each tree. The location of the pump needs to be considered to minimize the total length of the used tubes.
Write C program that can help the manager to do the above
Let the program input and output through file.
Structure of file NongTrai.in
– First line: N (number of trees).
– The following N lines, line #i (0 <= i <= N – 1): Xi Yi Li (Xi Yi: location of tree #i, Li : type of tree #i (0-coffee, 1-tea).
Structure of file NongTrai.out:
– Line #1: S0 S1 (S0: coffee tree count, S1: tea tree count).
– Line #2: Cmin (shortest fence length).
– Line #3: Dmin (minimum total length of used tubes).