圓圈游戲
【問題描述】
在無聊的時候，小 X和Sharon 會在紙上玩這樣一個游戲。
我們可以將紙看做一個平面直角坐標系。Sharon會先在上面畫出n 個圓，並
把每個圓的圓心以及半徑都告訴小X。Sharon 一向追求完美和簡約，因此她畫的
n 個圓中，任意兩個圓不會出現相交或相切的情況。小X 需要做的就是從這n
個圓中選出若干個圓，使得選出的任意一個圓都不被另一個選出的圓包含。游戲
的目標就是要選出盡量多的圓。
游戲一次一次進行著，小X 已經對游戲的規則感到了厭倦，所以他決定修
改游戲的規則。對於第i 個圓，我們定義它的價值為wi。新的游戲目標是使得選
出的圓價值和最大（不一定數量最多）。但是圓圈可能很多，或者圓圈的分布非
常奇怪，或者小X 還有別的事情要做。所以他只好拜托你來幫他求出這個最大
值了。
【輸入格式】
第一行一個整數n 表示圓圈的個數。
接下來n 行每行4 個整數xi，yi，ri，wi，分別表示第i 個圓圓心的橫坐標，
縱坐標，第i 個圓的半徑，第i 個圓的價值。
【輸出格式】
共一行包含一個整數，表示選出圓的最大價值和。
【樣例輸入】
3
3 4 2 3
6 4 7 5
9 4 1 4
【樣例輸出】
7
【樣例說明】
如果選擇價值最大的圓2，可以獲得的價值和為5。如果選擇圓1 和圓3，
雖然它們的單個價值都不是最大的，但價值和可以達到3+ 4 = 7。
試圖把它分解成上半圓與下半圓.
想象一條掃描線從左到右劃過
在任意時刻這條線都會與一些圓的上下半圓相交，相對關系不變
不妨把它看作括號匹配，於是只要求出它外面套的第一個括號……
值得一提，MAXN必須設計成原來的2倍，否則棧溢出……
我會研究出這是為什麼的。
[cpp]
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cctype>
#include<ctime>
#include<set>
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<n;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<b.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<a[j].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<b.x||(a.x==b.x&&a.is_ins<b.is_ins);}
}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()<B.y();}
};
multiset<node> 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<node>::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())<<endl,*/a[ask[i].no].fa=ask[i].no;
//cout<<T.size()<<' ';
T.insert(node(ask[i].no,0));/*cout<<T.size()<<' ';*/T.insert(node(ask[i].no,1));
//cout<<T.size()<<' ';
// for(set<node>::iterator it=T.begin();it!=T.end();it++) cout<< (it->no) <<" ";cout<<endl;
}
else T.erase(node(ask[i].no,0)),T.erase(node(ask[i].no,1));
}
}
//change
int edge[MAXN],pre[MAXN]={0},next[MAXN]={0},size=0;
void addedge(int u,int v)
{
edge[++size]=v;
next[size]=pre[u];
pre[u]=size;
}
struct st_el
{
int no,ans,fa,nowp,nowv;
st_el(){no=ans=fa=nowv=0;nowp=pre[no];}
st_el(int _no,int _fa):no(_no),fa(_fa){ans=nowv=0;nowp=pre[no];}
}st[MAXN];
int st_dfs(int u) //經證明，dfs不是導致棧溢的理由
{
st[1]=st_el(u,0);
int size=1;
while (size)
{
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 "<<v<<endl;
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 "<<st[size+1].no<<endl;
}
}
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<<a[i].fa<<' ';cout<<endl;
make_map2();
// For(i,n) cout<<a[i].fa<<' ';cout<<endl;
For(i,n) if (a[i].fa^i) addedge(a[i].fa,i),addedge(i,a[i].fa);
// For(i,n) cout<<a[i].fa<<' ';cout<<endl;
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<<i<<' ',*/ans+=st_dfs(i);
cout<<ans<<endl;
return 0;
}
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cctype>
#include<ctime>
#include<set>
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<n;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<b.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<a[j].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<b.x||(a.x==b.x&&a.is_ins<b.is_ins);}
}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()<B.y();}
};
multiset<node> 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<node>::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())<<endl,*/a[ask[i].no].fa=ask[i].no;
//cout<<T.size()<<' ';
T.insert(node(ask[i].no,0));/*cout<<T.size()<<' ';*/T.insert(node(ask[i].no,1));
//cout<<T.size()<<' ';
// for(set<node>::iterator it=T.begin();it!=T.end();it++) cout<< (it->no) <<" ";cout<<endl;
}
else T.erase(node(ask[i].no,0)),T.erase(node(ask[i].no,1));
}
}
//change
int edge[MAXN],pre[MAXN]={0},next[MAXN]={0},size=0;
void addedge(int u,int v)
{
edge[++size]=v;
next[size]=pre[u];
pre[u]=size;
}
struct st_el
{
int no,ans,fa,nowp,nowv;
st_el(){no=ans=fa=nowv=0;nowp=pre[no];}
st_el(int _no,int _fa):no(_no),fa(_fa){ans=nowv=0;nowp=pre[no];}
}st[MAXN];
int st_dfs(int u) //經證明，dfs不是導致棧溢的理由
{
st[1]=st_el(u,0);
int size=1;
while (size)
{
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 "<<v<<endl;
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 "<<st[size+1].no<<endl;
}
}
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<<a[i].fa<<' ';cout<<endl;
make_map2();
// For(i,n) cout<<a[i].fa<<' ';cout<<endl;
For(i,n) if (a[i].fa^i) addedge(a[i].fa,i),addedge(i,a[i].fa);
// For(i,n) cout<<a[i].fa<<' ';cout<<endl;
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<<i<<' ',*/ans+=st_dfs(i);
cout<<ans<<endl;
return 0;
}
