?

題目描述有些坑。。

題意：

　　有一條高速公路在x軸上，從（0,0）到（L,0）。周圍有一些村莊，希望能夠在高速公路上開通幾個出口，使得每個村莊到最近的出口距離小于D，求出最少需要開通多少個出口。

解題思路：

　　典型的區間問題，將每個點化為區間（x-sqrt(D^2-y^2),x+sqrt(D^2+y^2)），然后按區間右端點排序，依次對每個區間進行操作，如果該區間中已有出口則無需增加，若該區間沒有出口則取右端點為出口。

　　可以證明，這是最優方案，得到最少出口數。

#include<cstdio> #include<algorithm> #include<iostream> #include<cmath> #define eps 1e-6 using namespace std; int n,ans; double p,q,h,L,D; struct point{double x,y; }a[1000000]; bool cmp(point a,point b){if(a.y<b.y) return 1;return 0; } int main() { while(scanf("%lf%lf%d",&L,&D,&n)==3){for(int i=0;i<n;i++){scanf("%lf%lf",&p,&q);a[i].x=p-sqrt(fabs(D*D-q*q));a[i].y=p+sqrt(fabs(D*D-q*q));}sort(a,a+n,cmp);h=-100000;ans=0;for(int i=0;i<n;i++)if(!((h>a[i].x||fabs(h-a[i].x)<eps)&&(h<a[i].y||fabs(h-a[i].y<eps)))){h=a[i].y;if(h>L&&fabs(h-L)>eps) h=L;ans++;}printf("%d",ans); }return 0; }

轉載于:https://www.cnblogs.com/Mathics/p/3849356.html

總結

以上是生活随笔為你收集整理的POJ3485 区间问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。