Atcoder Beginner Contest 374 D题题解

一. 题目描述

题目传送门 - Atcoder Beginner Contest 374 D - Laser Marking

二. 思路分析

1.题目大意

在平面上给你一个激光（可看作一个点）和若干条线段（左右端点分别为 $a_i,b_i)$ ， $c_i,d_i)$ 。激光在线段上和非线段上的速度分别为 $s, t$ 。现在问激光从 $(0, 0)$ 开始，完全走过每条线段（即对于每条线段，激光必须从 $a_i,b_i)$ 连续不断地走到 $c_i,d_i)$ ）所用的最短时间是多少。

2.思路分析

先看数据范围：

$\le N \le 6$

发现线段的数量非常少，考虑枚举。

我们发现，激光的移动可以表示为以下几步：

激光从 $(0, 0)$ 移到一个线段端点。
激光沿线段从一个端点到另一个端点。
激光从该线段另一个端点到另一条线段的一个端点。
重复步骤 2,3 直到经过所有线段。

可以发现，我们只需要枚举线段的顺序，即先移到哪个线段端点，后移到哪个线段的端点。又因为对于每一条线段有两个端点，那么从两端出发都是可以的，也就需要在枚举每一条线段时再枚举两个端点即可。

3.要点提示

精度问题，存储与计算坐标时用 double。
两点 $A (x 1, y 1), B (x 2, y 2)$ 间距离公式（由勾股定理可得）：
$\sqrt{(x1-x2)^2+(y1-y2)^2}$
二进制枚举/深搜dfs 枚举线段的两个端点作为起始点。
起点在 $(0, 0)$ 。

三. 代码实现

#include <bits/stdc++.h>
using namespace std;
int n,t,s,p[8] = {0,1,2,3,4,5,6,7};
double a[8],b[8],c[8],d[8],ans = 1e9;
double dis(double a1,double b1,double a2,double b2)
{return sqrt((a1-a2)*(a1-a2)+(b1-b2)*(b1-b2));
}
int main()
{cin >> n >> s >> t;for (int i=1;i<=n;i++){cin >> a[i] >> b[i] >> c[i] >> d[i];}do{for (int i=0;i<(1<<(n+1));i++) //二进制枚举线段两个端点{double res = 0,l = 0,r = 0; //起点在(0,0)for (int j=1;j<=n;j++){if (i & (1 << j)){res += dis(l,r,a[p[j]],b[p[j]])/s;l = a[p[j]];r = b[p[j]];res += dis(l,r,c[p[j]],d[p[j]])/t;l = c[p[j]];r = d[p[j]];}else{res += dis(l,r,c[p[j]],d[p[j]])/s;l = c[p[j]];r = d[p[j]];res += dis(l,r,a[p[j]],b[p[j]])/t;l = a[p[j]];r = b[p[j]];}}if (res < ans) //更新最小值{ans = res;}}} while (next_permutation(p+1,p+n+1)); //全排列printf("%.20f",ans);return 0;
}