圆圈游戏(扫描线-圆的包含关系) - c++编程基础

{
int now=st[size].no;
bool flag=0;
if (st[size].nowv) st[size].ans+=st[size+1].ans;
for(;st[size].nowp;st[size].nowp=next[st[size].nowp])
{
int v=edge[st[size].nowp];
st[size].nowv=v;
if (v^st[size].fa)
{
st[size].nowp=next[st[size].nowp];
st[++size]=st_el(v,now);
// cout<<"add "< flag=1;
break;
}
}
if (!flag)
{
st[size].ans=max(st[size].ans,a[st[size].no].w);
a[st[size].no].ans=st[size].ans;
size--;
// cout<<"ers "< }
}
return a[u].ans;
}
int dfs(int u,int fa,int dep)
{
int ans=0;
Forp(u)
{
int &v=edge[p];
if (v^fa)
{
ans+=dfs(v,u,dep+1);
}
}
return max(a[u].w,ans);
}
int main()
{
freopen("circle.in","r",stdin);
freopen("circle.out","w",stdout);
scanf("%d",&n);
For(i,n) scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].r,&a[i].w),a[i].fa=i,a[i].dis=0;
// make_map1();
// For(i,n) cout< make_map2();
// For(i,n) cout< For(i,n) if (a[i].fa^i) addedge(a[i].fa,i),addedge(i,a[i].fa);
// For(i,n) cout<
long long ans=0;
// For(i,n) if (a[i].fa==i) ans+=dfs(i,0,0);
For(i,n) if (a[i].fa==i) /*cout<
cout<
return 0;
}

#include
#include
#include
#include
#include
#include
#include
#include

#include
#include
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i #define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define MAXN (200000+10)
long long sqr(int x){return (long long)x*x;}
struct cir
{
int x,y,r,w,fa,dis,ans;
friend bool operator<(cir a,cir b){return a.x friend bool operator==(cir a,cir b){return a.x==b.x;}
}a[MAXN];
int n;
void make_map1()
{
For(i,n)
Fork(j,i+1,n)
if (a[i].r^a[j].r)
{
long long dis=sqr(a[i].x-a[j].x)+sqr(a[i].y-a[j].y);
if (dis>sqr(a[i].r-a[j].r)) continue;
if (a[i].r {
if (a[i].fa==i||a[a[i].fa].r>a[j].r) a[i].fa=j;
}
else if (a[j].fa==j||a[a[j].fa].r>a[i].r) a[j].fa=i;
}
}
//change
struct comm
{
bool is_ins;
int no,x;
comm(){}
comm(bool _is_ins,int _no):is_ins(_is_ins),no(_no),x(a[_no].x+(_is_ins -1:1)*a[_no].r){}
friend bool operator<(comm a,comm b){return a.x }ask[MAXN*4];
int X;
struct node
{
bool is_up;
int no;
node(){}
node(int _no,bool _is_up):no(_no),is_up(_is_up){}
double y(){return (double)a[no].y+(double)(is_up 1:-1)*sqrt(sqr(a[no].r)-sqr(a[no].x-X));}
friend bool operator<(node A,node B){return A.y() };
multiset T;
void make_map2()
{
For(i,n) ask[i]=comm(1,i),ask[i+n]=comm(0,i);
sort(ask+1,ask+2*n+1);
For(i,2*n)
{
X=ask[i].x;
if (ask[i].is_ins)
{
set::iterator t2=T.upper_bound(node(ask[i].no,0));
if (t2!=T.begin()) --t2,a[ask[i].no].fa=(*t2).is_up a[t2->no].fa==t2->no ask[i].no:a[t2->no].fa:t2->no;
else /*cout<<(t2==T.end())< //cout< T.insert(node(ask[i].no,0));/*cout< //cout< // for(se

圆圈游戏(扫描线-圆的包含关系) (二)