圆圈游戏
鬼·烨弑
·
·
个人记录
考虑优化：
只有第一个包含自己的有用；
我们把圆劈成上半圆和下半圆；
按代表点坐标从小到大拍一下序
扫描线即可；
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
#include<set>
#include<cstring>
#include<cmath>
#include<algorithm>
#define eps 1e-5
#define ll long long
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
/*
名利真吾事，纷然过眼休。人生能有死，天道未曾修
百战身皆朽，群心志已酬。一场无限业，何处可优游
*/
const int N = 1e6 + 1000;
int n,tot,top,X;
int head[N],val[N],fa[N],f[N];
struct dian{int x,y,r;} p[N];
double S(int x){return 1.0 * x * x;}
struct node
{
int x,id,type;
int friend operator <(const node &A,const node &B)
{
return 1.0 * A.type * sqrt(S(p[A.id].r) - S(p[A.id].x - X) + eps) + 1.0 * p[A.id].y >
1.0 * B.type * sqrt(S(p[B.id].r) - S(p[B.id].x - X) + eps) + 1.0 * p[B.id].y;
}
} q[N];
set<node> s;
set<node>::iterator it;
struct LU{int nex,to;} a[N];
int cmp(const node &a,const node &b){return a.x < b.x;}
void add(int f,int t)
{
fa[t] = f;
a[++ tot] = LU{head[f],t};
head[f] = tot;
}
void dfs(int now)
{
for(int i = head[now];i;i = a[i].nex)
dfs(a[i].to),f[now] += f[a[i].to];
f[now] = max(f[now],val[now]);
}
int main()
{
freopen("circle.in","r",stdin);
freopen("circle.out","w",stdout);
n = read();
for(int i = 1;i <= n;i ++)
{
p[i].x = read(); p[i].y = read(); p[i].r = read(); val[i] = read();
q[++ top] = node{p[i].x - p[i].r,i,0};
q[++ top] = node{p[i].x + p[i].r,i,1};
}
sort(q + 1,q + 1 + top,cmp);
for(int i = 1;i <= top;i ++)
{
X = q[i].x;
if(q[i].type)
{
s.erase(node{0,q[i].id,1});
s.erase(node{0,q[i].id,-1});
}
else
{
s.insert(node{0,q[i].id,1});
s.insert(node{0,q[i].id,-1});
it = s.find(node{0,q[i].id,1});
if(it != s.begin())
{
it --;
if(it -> type == -1) add(fa[it -> id],q[i].id);
else add(it -> id,q[i].id);
}
else add(0,q[i].id);
}
}
dfs(0); cout << f[0] << "\n";
fclose(stdin); fclose(stdout);
}
```