首页 > 代码库 > UVALive 3835:Highway(贪心 Grade D)
UVALive 3835:Highway(贪心 Grade D)
VJ题目链接
题意：平面上有n个点，在x轴上放一些点，使得平面上所有点都能找到某个x轴上的点，使得他们的距离小于d。求最少放几个点。
思路：以点为中心作半径为d的圆，交x轴为一个线段。问题转换成用最少的店覆盖所有的线段。经典贪心。按右点从小到大排序，然后从左往右扫，每次选择区间右点就行了。
代码：
#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std;#define N 100100bool eqs(double a, double b) { return fabs(a-b) < 1e-5;}struct Seg{ double l, r; void get(int d) { int x, y; scanf("%d%d", &x, &y); double dx = sqrt(d*d-y*y+0.0); l = x - dx; r = x + dx; } bool operator < (const Seg &b) const { if (!eqs(r,b.r)) return r < b.r; return l < b.l; }}seg[N];int main(){ int l; while (scanf("%d", &l) != EOF) { int d; scanf("%d", &d); int n; scanf("%d", &n); for (int i = 0; i < n; i++) { seg[i].get(d); } sort(seg, seg+n); int cnt = 0; double now = -0x3f3f3f3f; for (int i = 0; i < n; i++) { if (now < seg[i].l) { now = seg[i].r; cnt++; } } printf("%d\n", cnt); } return 0;}
UVALive 3835:Highway(贪心 Grade D)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。