admin 管理员组

文章数量: 887021

Disks

题目链接

  • 题意：
    给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;
}


本文标签： Disks

版权声明：本文标题：Disks 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1688138404h183842.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。