ACM 贪心 Highway

朱雀 2022-06-10 23:41 180阅读 0赞

滴，集训第九天打卡。

感觉自己有些皮起来了，不是很有耐心做一些难题了...

今天的高效算法多是贪心做的。

**UVA 1615 Highway**

![20170725190837910][]

题目大意：在一条0-100的路上，可接受的D是50，有三个村庄，XY平面的点，在这条路上建加油站。使得村庄到加油站的距离不大于D，求加油站要建立多少才满足条件。

思路：先用数学方法，以村庄为圆心，D为半径画个圆，与公路相加的区间记录下来，将区间左右点排序，贪心得到加油站数量。

#include <stdio.h>
    #include <cmath>
    #include <algorithm>
    #include <string.h>
    using namespace std;
    int L,d;
    struct I
    {
        double l,r;
    }inter[10000];
    bool cmp(I a ,I b)
    {
        if(a.r==b.r)
    		return a.l<b.l;
    	return a.r<b.r;
    }
    int main()
    {
        double x,y,p,q;
        while(scanf("%d",&L)!=EOF)
        {
            scanf("%d",&d);
            int n;
            cin>>n;
            for(int i=1;i<=n;i++)
            {
                scanf("%lf%lf",&x,&y);
                inter[i].l=x-sqrt(d*d-y*y);
                inter[i].r=x+sqrt(d*d-y*y);
            }
            sort(inter+1,inter+1+n,cmp);
            int ans=1;
            p=inter[1].l,q=inter[1].r;
            int i=1;
    		while(i<=n)
    		{
    			if(inter[i].l>q)
    			{
    				ans++;
    				p=inter[i].l;
    				q=inter[i].r;
    			}
    			else
    			p=inter[i].l;
    			i++;
    		}
            cout<<ans<<endl;
        }

[20170725190837910]: /images/20220611/e969d5869a264420b16844b8354de106.png

发表评论取消回复

表情：

评论列表（有 0 条评论，180人围观）

还没有评论，来说两句吧...

相关阅读

相关 2019ACM-ICPC徐州网络赛-K- Center（简单贪心+map）

K- Center 2000ms 262144K You are given a point set with nn points on the 2D-plane, yo

Bertha 。/ 2023年06月05日 12:33/ 0 赞/ 8 阅读

相关 2019ACM-ICPC徐州网络赛-E-XKC's basketball team（set+贪心）

E-XKC's basketball team XKC , the captain of the basketball team , is directing a trai

电玩女神/ 2023年06月05日 12:33/ 0 赞/ 6 阅读

相关 uva 1615——Highway

题意：给定平面上n个点，和一个值D，要求在x轴上选出尽量少的点，使得对给定的点，都有一个点离他的欧几里德距离步超过D。思路：区间覆盖问题。以平面上的点为圆心，以

た入场券/ 2022年08月10日 00:58/ 0 赞/ 148 阅读

相关 poj 2485 Highways 【kruskal】

Highways <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

分手后的思念是犯贱/ 2022年08月09日 05:09/ 0 赞/ 59 阅读

相关 Highways

Highways <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td

比眉伴天荒/ 2022年07月14日 04:11/ 0 赞/ 139 阅读

相关 ACM 贪心 Crossing River

滴，集训第十四天打卡。台风终于来啦~ 凉快了很多啊，但是湿漉漉的也很麻烦... 噫，好气。 POJ 1700 Crossing River ![2017073016

我就是我/ 2022年06月11日 04:36/ 0 赞/ 168 阅读

相关 Highways

Highways <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td

旧城等待，/ 2022年06月11日 03:37/ 0 赞/ 182 阅读

相关 ACM 贪心 Highway

滴，集训第九天打卡。感觉自己有些皮起来了，不是很有耐心做一些难题了... 今天的高效算法多是贪心做的。 UVA 1615 Highway ![201707251908

朱雀/ 2022年06月10日 23:41/ 0 赞/ 181 阅读

相关 poj-1751-Highways-最小生成树

Highways Description The island nation of Flatopia is perfectly flat. Unfortunatel

偏执的太偏执、/ 2022年06月06日 09:05/ 0 赞/ 232 阅读

相关 poj--2485--Highways

Highways <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td

爱被打了一巴掌/ 2022年06月03日 01:17/ 0 赞/ 240 阅读