題目鏈接：http://poj.org/problem?id=3485

題意：X軸上公路從0到L，X軸上下有一些點(diǎn)給出坐標(biāo)代表村莊，問在公路上最少建幾個(gè)出口才能使每個(gè)村莊到出口的距離不超過D。

以村莊為圓心，半徑為 d 畫圓，與公路相交，得到一個(gè)一個(gè)區(qū)間，這么選點(diǎn)呢？

按照區(qū)間右端點(diǎn)排序，第一個(gè)點(diǎn)，選擇第一條線段的右端點(diǎn)，當(dāng)前位置就在這里，已經(jīng)（很）靠后了，拿這個(gè)點(diǎn)去查看以后的線段，看是不是符合。

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

?

轉(zhuǎn)載于:https://www.cnblogs.com/TreeDream/p/6636667.html

總結(jié)

以上是生活随笔為你收集整理的poj 3485 区间选点的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。