题解 【CF15A Cottage Village】

TRZ_2007

2021-09-05 16:24:29

Solution

**[题解 【CF15A Cottage Village】](https://www.luogu.com.cn/problem/CF15A)** # Solution 这题就是一个数学问题…… 我们先把所有的房子按照左端点排序,得到他们位置的相对关系,注意,这里不能用中心位置排,因为房子的边长是一个不确定的量。 好接下来我们考虑如何计数。 - 1:最左边的左和最右边的右肯定是可以放的。 - 2:两个房子中间的间隔如果正好是我要建的房子的边长,那么在这里我就只有一种建造方法。 - 3:两个房子中间的间隔如果大于我的房子的边长,那么我可以建在靠左房子的右边和靠右房子的左边,有两种建造方法。 - 4:两个房子中间的间隔如果小于我的房子的边长,那么显然我在这里不能造房子。 综合上述分类,加一下就可以了,注意卡精度。 # Code ```cpp #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; } ```