比赛场次 508
比赛名称 SYOI2022 Round2
比赛状态 已结束比赛成绩
开始时间 2022-06-15 18:30:00
结束时间 2022-06-16 21:05:00
开放分组 全部用户
注释介绍
题目名称 Looking for Order
输入输出 lenepack.in/out
时间限制 5000 ms (5 s)
内存限制 512 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
Gravatar锝镆氪锂铽 AAAAAAAAAA 1.166 s 133.74 MiB 100
Gravatarop_组撒头屯 AAATTTTTAA 27.929 s 4.01 MiB 50
Gravatar该账号已注销 WWWWWWWWWW 0.000 s 0.00 MiB 0
GravatarHeSn WWWTTTTTTT 35.082 s 5.74 MiB 0

Looking for Order

★★   输入文件:lenepack.in   输出文件:lenepack.out   简单对比
时间限制:5 s   内存限制:512 MiB

【题目描述】

Lena喜欢秩序井然的生活。一天,她要去上大学了。突然,她发现整个房间乱糟糟的——她的手提包里的物品都散落在了地上。

她想把所有的物品都放回她的手提包。但是,这里有一点问题:她一次最多只能拿两个物品,她也不能移动她的手提包。

并且,因为她爱整洁的习惯,如果她拿起了一个物品,她也不能将它放在其他地方,除非放回她的手提包。

Lena把她的房间划分为了一个平面直角坐标系。现在Lena给你她的手提包和每个散落的物品的坐标(当然,一开始的时候她就和手提包站在一个地方)。

她从坐标 $(x_1,y_1)$ 走到坐标 $(x_2,y_2)$ 需要用 $(x_1-x_2)^2+(y_1-y_2)^2$ 单位的时间。

现在,Lena将告诉你她的房间的情况,请你为Lena找到一个拾起每个物品的顺序,使她拾起所有物品所需的总时间最小。当然,Lena最后需要返回她的手提包。

【输入格式】

输入文件的第一行为Lena的手提包的坐标 $x_s$,$y_s$。

第二行为一个正整数 $n$,表示总的需要拾起的物品数。

接下来的 $n$ 行每行包括两个整数,表示每个物品的坐标。

【输出格式】

输出一行,一个正整数,表示Lena拾起所有物品所需的最小时间。

【样例输入1】

0 0
2
1 1
-1 1

【样例输出1】

8

【样例输入2】

1 1
3
4 3
3 4
0 0

【样例输出2】

32

【样例说明】

略。

【数据规模与约定】

对于 30% 的数据,$1 \le n \le 5$

对于 100% 的数据,$1 \le n \le 24$,$0 \le |x_s|,|y_s| \le 100$

【来源】

CF8C

翻译来自洛谷