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

圆圈游戏
【问题描述】
在无聊的时候，小 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
#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(set::iterator it=T.begin();it!=T.end();it++) cout<< (it->no) <<" ";cout< }
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)

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