样例:
考试的时候没时间打了,随便敲了敲就交上去了,没想到竟然编译错误,忘定义n了23333
自己测了测能骗20分hhhh
考虑每个圆对答案的贡献,当一个圆被小圆内切的时候,分成了两半,对答案的贡献就是2。其余情况是1。
按左端点从小到大排序,左端点相同则按右端点由大到小。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define pos(i,a,b) for(int i=(a);i<=(b);i++) #define N 301000 int n; struct haha{ int l,r,o; }cun[N]; int ans[N]; bool aaa(const haha &a,const haha &b){ if(a.l==b.l) return a.r>b.r; return a.l<b.l; } int cnt; void dfs(int now){ cnt=now+1;int maxr=cun[now].l; int flag=0; while(cnt<=n&&maxr<cun[now].r){ if(cun[cnt].r>cun[now].r) break; if(!flag&&cun[cnt].l==maxr){ maxr=max(maxr,cun[cnt].r); } else flag=1; dfs(cnt); } if(maxr==cun[now].r){ ans[now]=2; } else ans[now]=1; } int sum; int main(){ scanf("%d",&n); pos(i,1,n){ int x,y; scanf("%d%d",&x,&y); cun[i].o=x;cun[i].l=x-y;cun[i].r=x+y; } sort(cun+1,cun+n+1,aaa); pos(i,1,n){ if(!ans[i]) dfs(i); sum+=ans[i]; } cout<<sum+1; return 0; }