首页 > 代码库 > Disks

Disks

2024-07-17 20:44:06   219人阅读

题目链接

  • 题意：
    给n个圆形盘子的半径，按照顺序一个一个放到x轴正无穷处（与x轴相切），然后向x轴负方向滚动直到碰到第一个盘子或者接触到y轴就停止。输出哪些盘子去掉后，右边界不会变小
  • 分析：
    这个题的总体思路比较简单，就是枚举出之前所有的盘子就可以知道当前盘子的位置了。既然要去掉后右边界不变，那么可以先找到右边界上的盘子，问题来了，如果有多个呢？可以想到，选id较小的那个就可以了，因为这个圆的半径必然比较大，和之前的盘子肯定有接触；然后就是看一下和当前盘子接触的有哪些，如果有多个呢？同样的，还是找id较小的那个，因为半径大，和之前的盘子相切
    这个题难点不在计算，而在于多种情况的处理上
const double eps = 1e-6;
const int maxn = 1100;

inline int dcmp(double x)
{
    if (fabs(x) < eps) return 0;
    return x < 0 ? -1 : 1;
}
struct Point
{
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
};
struct Circle
{
    Point p;
    double r;
} ipt[maxn];

double x[maxn];
int pre[maxn];
bool vis[maxn];
int ans = 0;

void dfs(int u)
{
    ans--;
    vis[u] = true;
    if (pre[u] == u)
        return;
    if (!vis[pre[u]])
        dfs(pre[u]);
}

int main()
{
    //freopen("0.txt", "r", stdin);
    int n;
    while (~RI(n))
    {
        ans = n;
        FE(i, 1, n)
        {
            scanf("%lf", &ipt[i].r);
            ipt[i].p.y = ipt[i].r;
            pre[i] = i;
            vis[i] = false;
        }
        ipt[1].p.x = ipt[1].r;
        double Max = ipt[1].p.x + ipt[1].r;
        int id = 1;
        FE(i, 2, n)
        {
            double xmax = ipt[i].r;
            FE(j, 1, i - 1)
            {
                x[j] = 2 * sqrt(ipt[i].r * ipt[j].r) + ipt[j].p.x;
                if (dcmp(xmax - x[j]) < 0)
                    xmax = x[j];
            }
            FE(j, 1, i - 1)
            {
                if (dcmp(x[j] - xmax) == 0)
                {
                    pre[i] = j;
                    break;
                }
            }
            ipt[i].p.x = xmax;
            if (dcmp(ipt[i].p.x + ipt[i].r - Max) > 0)
            {
                Max = ipt[i].p.x + ipt[i].r;
                id = i;
            }
        }
        dfs(id);
        WI(ans);
        FE(i, 1, n)
        {
            if (!vis[i])
                WI(i);
        }
    }
    return 0;
}


联系
我们