题目介绍题目解读这道题有两个地方需要注意1.自己的坐标不是固定的2.子弹射出后可以贯穿轨迹上的所有人于是乎 题意就是试找出最少的直线能连接所有的点洛谷有一道题和此题同类型题不过直线方程改为了曲线方程题目链接解题思路首先两个点可以确定一条线我们可以依次枚举每个点此时有三种情况1.前面已经构成的线已经把这个点给覆盖了2.从被存起来的点中选择一个点构成一条新的线3.把这个点存起来暂时不做处理由于平行x、y轴的直线需要特殊存储所以需要存储三种直线具体思路在代码中AC代码#include bits/stdc.h using namespace std; const int maxn 15; int n; double X[maxn 1], Y[maxn 1]; //敌人坐标 double tx[maxn 1], ty[maxn 1]; //存起来的敌人坐标 double K[maxn 1], B[maxn 1]; //直线方程 ykxb的 k和b double k0[maxn 1], k1[maxn 1]; //k0:存储斜率为0的直线的y k1存储斜率为无穷大的直线的x int ans 10000; bool isZero(double x) { //判断是否为0 if (fabs(x) 1e-6) { return true; } return false; } void dfs(int id, int u, int u0, int u1, int v) { //id:当前敌人, u:直线方程的个数, u0:斜率为0的直线的个数, // u1:斜率为无穷大的直线的个数, v:存起来的敌人的个数 if (u u0 u1 v ans) { //已经比答案大 return; } if (id n) { //更新答案 ans u u0 u1 v; return; } bool flag false; //判断是否被前面的直线方程的连到过 for (int i 1; i u; i) { if (isZero(Y[id] - K[i] * X[id] - B[i])) { //被前面的线连到过 dfs(id 1, u, u0, u1, v); flag true; break; } } //判断是否被前面的斜率为0的直线的连到过 if (!flag) { for (int i 1; i u0; i) { if (Y[id] k0[i]) { dfs(id 1, u, u0, u1, v); flag true; break; } } } //判断是否被前面的斜率为无穷大的直线的连到过 if (!flag) { for (int i 1; i u1; i) { if (X[id] k1[i]) { dfs(id 1, u, u0, u1, v); flag true; break; } } } //没有被连过 if (!flag) { //跟被存起来的人连线 for (int i 1; i v; i) { if (isZero(Y[id]- ty[i])) { //能构成斜率为0的线 k0[u0 1] Y[id]; //别忘了把这个直线存起来 double q tx[i], w ty[i]; for (int j i; j v; j) { //把这个被存起来的敌人移出来 tx[j] tx[j 1]; ty[j] ty[j 1]; } dfs(id 1, u, u0 1, u1, v - 1); for (int j v; j i; j--) { //回溯被存起来的敌人 tx[j] tx[j - 1]; ty[j] ty[j - 1]; } tx[i] q; ty[i] w; } if (isZero(X[id]-tx[i])) { //能构成斜率为0的线 k1[u1 1] X[id]; //存起来 double q tx[i], w ty[i]; for (int j i; j v; j) { tx[j] tx[j 1]; ty[j] ty[j 1]; } dfs(id 1, u, u0, u1 1, v - 1); for (int j v; j i; j--) { tx[j] tx[j - 1]; ty[j] ty[j - 1]; } tx[i] q; ty[i] w; } if (!isZero(Y[id] - ty[i]) !isZero(X[id] - tx[i])) { //能构成直线方程 double k (Y[id] - ty[i]) / (X[id] - tx[i]); double b Y[id] - k * X[id]; K[u 1] k; B[u 1] b; double q tx[i], w ty[i]; for (int j i; j v; j) { tx[j] tx[j 1]; ty[j] ty[j 1]; } dfs(id 1, u 1, u0, u1, v - 1); for (int j v; j i; j--) { tx[j] tx[j - 1]; ty[j] ty[j - 1]; } tx[i] q; ty[i] w; } } //选择存起来 tx[v 1] X[id]; ty[v 1] Y[id]; dfs(id 1, u, u0, u1, v 1); } } int main() { scanf(%d, n); for (int i 1; i n; i) { scanf(%lf%lf, X[i], Y[i]); } dfs(1, 0, 0, 0, 0); printf(%d, ans); }