题解 【CF15A Cottage Village】

Solution

这题就是一个数学问题……
我们先把所有的房子按照左端点排序，得到他们位置的相对关系，注意，这里不能用中心位置排，因为房子的边长是一个不确定的量。
好接下来我们考虑如何计数。

• 1：最左边的左和最右边的右肯定是可以放的。
• 2：两个房子中间的间隔如果正好是我要建的房子的边长，那么在这里我就只有一种建造方法。
• 3：两个房子中间的间隔如果大于我的房子的边长，那么我可以建在靠左房子的右边和靠右房子的左边，有两种建造方法。
• 4：两个房子中间的间隔如果小于我的房子的边长，那么显然我在这里不能造房子。

综合上述分类，加一下就可以了，注意卡精度。

Code

#include <cstdio>
#include <algorithm>

const int N = 1009;

int n,ans = 2; double t,d;  //最左边和最右边肯定可以

struct node {
    double xi,l,r;  //记录位置，左右端点
}p[N];

bool cmp(node u,node v) {   //按左端点排序
    if(u.l != v.l) return u.l < v.l;
    else return u.r < v.r;
}

int main() {
    scanf("%d %lf",&n,&t);
    for(int i = 1;i <= n;i++) {
        scanf("%lf %lf",&p[i].xi,&d);
        p[i].l = p[i].xi - d / 2; p[i].r = p[i].xi + d / 2;
    }
    std::sort(p + 1,p + n + 1,cmp);
    for(int i = 2;i <= n;i++) {
        if(p[i].l - p[i - 1].r > t) ans += 2;
        if(p[i].l - p[i - 1].r == t) ans++;
    }
    printf("%d\n",ans);
    return 0;
}