noip模拟赛 动态仙人掌（并查集，贪心）

思路：

贪心+并查集

因为45‘，所以可以很方便的算出每个仙人掌的最晚起跳（左端点）

右端点自然也能出来

先按左端点排序

如果他右面的和他相交，就更新

用并查集维护这个更新的关系

更新的同时维护高就好了

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rii register int i
#define rij register int j
using namespace std;
struct xrz{
    int x,l,r;
}x[300005],y[300005];
int n,bj[300005],fa[300005],ans;
int find(int ltt)
{
    if(fa[ltt]!=ltt)
    {
        fa[ltt]=find(fa[ltt]);
    }
    return fa[ltt];
}
bool cmp1(xrz lk,xrz kl)
{
    return lk.l<kl.l;
}
void gx(int l,int r)
{
    x[l].l=min(x[l].l,x[r].l);
    x[l].r=max(x[r].r,x[l].r);
}
int main()
{
    freopen("dinosaur.in","r",stdin);
    freopen("dinosaur.out","w",stdout);
    scanf("%d",&n);
    for(rii=1;i<=n;i++)
    {
        int h;
        scanf("%d%d",&x[i].x,&h);
        x[i].l=x[i].x-h;
        x[i].r=x[i].x+h;
    }
    sort(x+1,x+n+1,cmp1);
    for(rii=1;i<=n;i++)
    {
        fa[i]=i;
    }
    for(rii=1;i<=n-1;i++)
    {
        int ltt=find(i);
        int kkk=find(i+1);
        if(x[ltt].r>x[kkk].l)
        {
            gx(ltt,kkk);
            fa[kkk]=ltt;
            if(x[ltt].l<0)
            {
                cout<<"-1";
                return 0;
            }
        }
        ans=max(ans,x[ltt].r-x[ltt].l);
    }
    ans=max(ans,x[n].r-x[n].l);
    double an=(double)ans/2;
    printf("%.1lf",an);
    return 0;
}