Niuniu has N directed segments. Each segment has one color. He wants to make a powerful sword by connecting the segments. He can choose at most K segments. He isn’t allowed to choose more than one segment from each color, or rotate segments. The powerfulness of the sword is calculated by the square of the distance between the beginning of the first segment and the end of the last segment. Niuniu wants to know the largest powerfulness when K = 1,…, N.
输入描述:
The input has the format as described below.Nx1 y1 c1x2 y2 c2...xn yn cnN is the number of segments. (1 ≤ N ≤ 1000) The ith segment starts at (0,0), ends at(xi,yi), with color ci. (-1000000 ≤ xi,yi ≤ 1000000, xi2+yi20, 1 ≤ ci ≤ n)
输出描述:
You should output the answers in one line, separated by a space.
示例1
输入
4
1 2 1
2 1 1
2 3 2
3 1 2
示例3
输入
10
1 4 1
-2 3 2
3 2 1
2 5 3
-4 2 3
-3 3 1
3 1 2
-10 -10 4
7 7 4
7 7 5
输出
200 392 617 818 976 976 976 976 976 976
备注:
You can consider the segment in this problem as 2D vector.
加载中...