您现在的位置: 华盟网 >> 编程 >> Vc >> 正文

圆圈游戏中扫描线与圆关系

2013/8/8 作者:不详 来源: 华盟收集
导读 【问题描述】  在无聊的时候,小 X和Sharon 会在纸上玩这样一个游戏。  我们可以将纸看做一个平面直角坐标系。Sharon会先在上面画出n 个圆,并把每个…

  【问题描述】

  在无聊的时候,小 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。

   \

[NextPage]

  试图把它分解成上半圆与下半圆.

  想象一条扫描线从左到右划过在任意时刻这条线都会与一些圆的上下半圆相交,相对关系不变不妨把它看作括号匹配,于是只要求出它外面套的第一个括号……

  值得一提,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();

[NextPage]

 // 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;

  }

                  微信群名称:华盟黑白之道二群   华盟-黑白之道⑦QQ群: 9430885

  • 上一篇编程:

  • 下一篇编程:
  • 网友评论
      验证码
     

    关注

    分享

    0

    讨论

    2

    猜你喜欢

    论坛最新贴

    编程栏目相关内容

      没有相关编程