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.
[编程题]Connecting segments
- 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
输入描述:
The input has the format as described below.
N
x1 y1 c1
x2 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+yi2>0, 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
输出
13 34 34 34
示例2
输入
2 1 1 1 -1 -1 2
输出
2 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.
这道题你会答吗？花几分钟告诉大家答案吧！
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
