Coin Slider

题目大意

膜拜一位霓虹大佬%%%%

平面上有一堆不重叠的硬币.
给定硬币的起点和终点,问最多可以把多少个硬币从起点直线移动到终点,且不会与其他硬币碰撞.

解析

状压$dp$+计算几何
一个硬币能否移动的条件为:第$i$枚硬币的起点和终点的连线L,与第$j$个硬币中心的距离$d$是否大于这俩个硬币半径的和.
即$distance(L,O_j)<r_j+r_i$
将每一个硬币是否移动过压缩为$0$和$1$,每次要移动$i_{th}$硬币时,先判断答案这一位是不是$1$.
再根据答案数中的二进制位判断$j_{th}$这个圆是在终点还是起点.
最后再判断能否移动,更新答案即可.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100 + 10;
const double eps = 1e-5;
const double pi = acos(-1.0);
typedef struct point vec;
struct point {
    double x, y;
    point() {}
    point(double a, double b)
    {
        x = a, y = b;
    }
    point operator*(const point& i_T) const
    {
        return point(x * i_T.x, y * i_T.y);
    }
    point operator*(double u) const
    {
        return point(x * u, y * u);
    }
    point operator/(double u) const
    {
        return point(x / u, y / u);
    }
    bool operator>(const point a) const
    {
        return x == a.x ? y > a.y : x > a.x;
    }
    point operator-(const point a) const
    {
        return point(x - a.x, y - a.y);
    }
    point operator+(const point a) const
    {
        return point(x + a.x, y + a.y);
    }
    point operator+(double a) const
    {
        return point(x + a, y + a);
    }
    bool operator<(const point a) const
    {
        return y == a.y ? x < a.x : y < a.y;
    }
    friend ostream& operator<<(ostream& out, point& a)
    {
        cout << a.x << ',' << a.y;
        return out;
    }
    friend istream& operator>>(istream& in, point& a)
    {
        in >> a.x >> a.y;
        return in;
    }
};
typedef struct Line Segment; //线段Segment
struct Line { //直线
    vec a, b;
    Line(point _a = point(), point _b = point())
        : a(_a)
        , b(_b)
    {
    }
    friend istream& operator>>(istream& in, Line& a)
    {
        cin >> a.a >> a.b;
        return in;
    }
    friend ostream& operator<<(ostream& out, Line& a)
    {
        out << a.a << ' ' << a.b;
        return out;
    }
};
struct cirles {
    point o;
    double r;
    cirles(point _o = point(), double _r = 0.0)
        : r(_r)
        , o(_o)
    {
    }
    point Point(double t) //圆上任意一点
    {
        return point(o.x + r * cos(t), o.y + r * sin(t));
    }
    friend istream& operator>>(istream& in, cirles& a)
    {
        in >> a.o >> a.r;
        return in;
    }
    friend ostream& operator<<(ostream& out, cirles& a)
    {
        out << a.o << ' ' << a.r;
        return out;
    }
};
struct ceshi2 {
    cirles s, t;
};
int dayu_dengyu(double x, double y)
{
    if (fabs(x - y) < eps || x > y)
        return 1;
    return 0;
}
int zhengfu(double x)
{
    if (fabs(x) < eps)
        return 0;
    return x > 0 ? 1 : -1;
}
double changdu(vec a) //长度
{
    return sqrt(a.x * a.x + a.y * a.y);
}
double dianji(vec A, vec B) //点积
{
    return A.x * B.x + A.y * B.y;
}
double dian_dao_xianduan(Segment l, point c) //点到线段的距离
{
    double L = changdu(l.b - l.a);
    double r = dianji(l.b - l.a, c - l.a) / (L * L);

    if (zhengfu(r) == -1) {
        return changdu(c - l.a);
    } else if (dayu_dengyu(r, 1)) {
        return changdu(c - l.b);
    } else {
        double L = r * changdu(l.b - l.a), l2 = changdu(c - l.a);
        return sqrt(l2 * l2 - L * L);
    }
}
int query(int x)
{
    int cnt = 0;
    while (x > 0) {
        cnt++;
        x -= (x & -x);
    }
    return cnt;
}
int dp[1 << 22], N;
ceshi2 K[MAXN];
int main()
{
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> K[i].s.r >> K[i].s.o >> K[i].t.o;
        K[i].t.r = K[i].s.r;
    }

    dp[0] = 1;
    for (int msk = 0; msk < (1 << N); msk++)
        if (dp[msk])
            for (int i = 0; i < N; i++)
                if (!(msk & (1 << i))) { //如果硬币被移动过了
                    
                    //判断其他硬币位置是在s,还是在t
                    vector<cirles> V;
                    for (int j = 0; j < N; j++)
                        if (i != j)
                            if (msk & (1 << j))
                                V.push_back(K[j].t);
                            else
                                V.push_back(K[j].s);

                    //判断该硬币能否移动

                    Line l(K[i].s.o, K[i].t.o);
                    int ok = 1, n = V.size();
                    for (int j = 0; j < n; j++) {
                        double d = dian_dao_xianduan(l, V[j].o);
                        if (d < K[i].s.r + V[j].r - eps)
                            ok = 0;
                    }
                    if (ok)
                        dp[msk + (1 << i)] = 1;
                }

    int ans = 0;
    for (int msk = 0; msk < (1 << N); msk++)
        if (dp[msk])
            ans = max(ans, query(msk));
    cout << ans << endl;
    return 0;
}