poj 3485 区间选点

题目链接：http://poj.org/problem?id=3485

题意：X轴上公路从0到L，X轴上下有一些点给出坐标代表村庄，问在公路上最少建几个出口才能使每个村庄到出口的距离不超过D。

以村庄为圆心，半径为 d 画圆，与公路相交，得到一个一个区间，这么选点呢？

按照区间右端点排序，第一个点，选择第一条线段的右端点，当前位置就在这里，已经（很）靠后了，拿这个点去查看以后的线段，看是不是符合。

1 #include <cstdio> 2 #include <cmath> 3 #include <algorithm> 4 5 using namespace std; 6 7 const int maxn = 10005; 8 9 struct Point 10 { 11 double x,y; 12 } points[maxn]; 13 14 struct Line 15 { 16 double x,y; 17 } lines[maxn]; 18 19 bool cmp(Line a,Line b) 20 { 21 return a.y < b.y; 22 } 23 24 int main() 25 { 26 double s; 27 double d; 28 while(~scanf("%lf%lf",&s,&d)) 29 { 30 int n; 31 scanf("%d",&n); 32 for(int i=0; i<n; i++) 33 { 34 scanf("%lf%lf",&points[i].x,&points[i].y); 35 lines[i].x = points[i].x - sqrt(d*d-points[i].y*points[i].y); 36 lines[i].y = points[i].x + sqrt(d*d-points[i].y*points[i].y); 37 } 38 39 sort(lines,lines+n,cmp); 40 int ans = 1; 41 double cur = lines[0].y; 42 for(int i=1; i<n; i++) 43 { 44 if(cur>=lines[i].x&&cur<=lines[i].y) 45 continue; 46 else 47 { 48 cur = lines[i].y; 49 ans++; 50 } 51 } 52 53 printf("%d\n",ans); 54 } 55 return 0; 56 } View Code

 

转载于:https://www.cnblogs.com/TreeDream/p/6636667.html

总结

以上是生活随笔为你收集整理的poj 3485 区间选点的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。