首页 > 代码库 > POJ3485 区间问题

POJ3485 区间问题

2024-07-12 09:01:16   214人阅读

 

题目描述有些坑。。

题意：

　　有一条高速公路在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-6using 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;}


联系
我们