首页 > ACM题库 > HDU-杭电 > hdu 2477 Crop circles[解题报告]hoj
2014
01-26

hdu 2477 Crop circles[解题报告]hoj

Crop circles

问题描述 :

Is there really a monster living in Loch Ness?
Did the lost city of Atlantis ever exist?
Are UFOs tricks of the light, or actually vehicles from outer space?
Who is responsible for the strange patterns called crop circles――clever hoaxers or alien beings?

As we can see, there are so many mysterious places, creatures and events in the world which puzzled people for centuries. In this problem, we won’t go through all that puzzles. Which we are interested in is this one — crop circles.

You have probably seen pictures of crop circles. (i.e. see above) They are circular patterns which mysteriously appear in fields of crop, such as wheat and barley. For research, we model these patterns as N circles in the plane and number them with 1, 2, …, N. Each of them has its center (Xi, Yi), radius Ri and an importance value Vi which is evaluated by the scientists.

After our observation, we found that there aren’t any two circles touch each other in the crop circles. But it’s possible that a circle is completely within another one. When we are in a certain circle, we should pass through its borderline once in order to get out from it.

For two distinct circles A and B, if one can go to B from A without passing through more than K borderlines, we say that A and B are connected. Here comes the problem: For all connected cycle pairs (A, B), what’s the maximum difference of the importance value between them? The difference of the importance value between A and B can be defined as |VA � VB|.
For example, look at the picture below. For K = 3, the optimal solution is to select the circle 1 and 3 which make the difference of importance value 220. And there are 3 borderlines between circle 1 and 3.
|V5 � V1| = 300, which is larger than 220, but circle 5 and circle 1 are not connected. There’re 4 borderlines between them, so we won’t consider these kinds of pairs.

输入:

The first line of input gives the number of cases T <= 20. T test cases follow.
    The first line of each case contains two integers N, K as described above. (1 < N < 50001, 1 < K < 101).
Next follow N lines, each contains four integers Xi, Yi, Ri, Vi, separated by spaces. The i-th line specifying the information of the i-th circle, where (Xi, Yi) are the coordinates of the center, Ri specifies the radius and Vi is the importance value.
(0 < Ri <= 2 * 10^8, -10^9 < Xi, Yi, Vi < 10^9)

输出:

The first line of input gives the number of cases T <= 20. T test cases follow.
    The first line of each case contains two integers N, K as described above. (1 < N < 50001, 1 < K < 101).
Next follow N lines, each contains four integers Xi, Yi, Ri, Vi, separated by spaces. The i-th line specifying the information of the i-th circle, where (Xi, Yi) are the coordinates of the center, Ri specifies the radius and Vi is the importance value.
(0 < Ri <= 2 * 10^8, -10^9 < Xi, Yi, Vi < 10^9)

样例输入:

2
5 3
10 10 1 -200
0 0 8 10
-2 2 2 20
3 -3 3 2
3 -3 1 100
3 2
-200 0 1 0
0 0 100 2
200 0 1 10

样例输出:

Case 1: 220
Case 2: 10

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=50500;
const double zero=1e-8;
const double inf=1e10;

int n,K,m,L,tot,root,ans;
int E[maxn],pre[maxn],fst[maxn];
int V[maxn],ft[maxn],pl[maxn],pr[maxn],f[maxn][110],g[maxn][110],h[maxn],q[maxn];

struct Event
{
       double x,y,r,px; int id,v;
       Event(){};
       Event(double _x,double _y,double _r,double _px,int i,int _v) {x=_x; y=_y; r=_r; px=_px; id=i; v=_v;};
       bool operator <(const Event &rhs)const
       {
            return px+zero<rhs.px;
       }
       double gety(double x0,int v0)
       {
              if(fabs(x0-x)+zero>=r) return y;
              double tmp=sqrt(r*r-(x-x0)*(x-x0));
              if(v0==0) return y-tmp; else return y+tmp;
       }
}Et[2*maxn];

struct Tree
{
       int ft,lc,rc,x,v;
       void clear() {ft=lc=rc=x=v=0;}
}tr[4*maxn];

struct Splay
{
       void New(int i)//0:down 1:up
       {
            tr[++tot].clear(); tr[tot].x=i; tr[tot].v=0; tr[tot].rc=tot+1; pl[Et[i].id]=tot;
            tr[++tot].clear(); tr[tot].x=i; tr[tot].v=1; tr[tot].ft=tot-1; pr[Et[i].id]=tot;
       }
	   
       void rotate(int x)
       {
            int y=tr[x].ft,z=tr[y].ft;
            if(tr[z].lc==y) tr[z].lc=x; else tr[z].rc=x;
            tr[x].ft=z; tr[y].ft=x;
            if(tr[y].lc==x) tr[y].lc=tr[x].rc,tr[tr[x].rc].ft=y,tr[x].rc=y;
               else tr[y].rc=tr[x].lc,tr[tr[x].lc].ft=y,tr[x].lc=y;
       }
	   
       void splay(int x,int p)
       {
            int fa=tr[p].ft;
            while(tr[x].ft!=fa)
            {
                  int y=tr[x].ft,z=tr[y].ft;
                  if(z==fa) {rotate(x); continue;}
                  if((tr[y].lc==x)^(tr[z].lc==y)) rotate(x); else rotate(y);
                  rotate(x);
            }
            if(p==root) root=x;
       }
	   
       int select(int i)
       {
           int p=root,ql=p,qr=p; double x=Et[i].px,y=Et[i].y;
           while(p>0)
           {
                 int id=tr[p].x,v=tr[p].v; double y0;
                 if(id==0) y0=v?inf:-inf; else y0=Et[id].gety(x,v);
                 if(y0+zero<y) ql=p,p=tr[p].rc; else qr=p,p=tr[p].lc;
           }
           splay(ql,root); splay(qr,tr[root].rc);
           return qr;
       }
	   
       int getpre(int x)
       {
           splay(x,root);
           int p=tr[x].lc; while(tr[p].rc) p=tr[p].rc;
           return p;
       }
	   
       int getnext(int x)
       {
           splay(x,root);
           int p=tr[x].rc; while(tr[p].lc) p=tr[p].lc;
           return p;
       }
}Tr;

int get()
{
    int f=0,v=0; char ch;
    while(!isdigit(ch=getchar())) if(ch=='-') break;
    if(ch=='-') f=1; else v=ch-48;
    while(isdigit(ch=getchar())) v=v*10+ch-48;
    if(f) return -v; else return v;
}

void init()
{
     m=0; int x,y,r;
     n=get(); K=get()+1;
     for(int i=1;i<=n;i++)
     {
         x=get(); y=get(); r=get(); V[i]=get();
         Et[++m]=Event(x,y,r,x-r,i,1);
         Et[++m]=Event(x,y,r,x+r,i,0);
     }
}

void add(int a,int b)
{
     E[++L]=b; pre[L]=fst[a]; fst[a]=L;
}

void build()
{
     tot=L=0; root=1;
     memset(fst,0,sizeof(fst));
     tr[0].clear(); Tr.New(0);
	 sort(Et+1,Et+m+1);
     for(int i=1;i<=m;i++)
         if(Et[i].v)
         {
		    Tr.New(i);
            int k=Tr.select(i); tr[tot-1].ft=k; tr[k].lc=tot-1;
            ft[Et[i].id]=(tr[k].v)?Et[tr[k].x].id:ft[Et[tr[k].x].id];
            add(ft[Et[i].id],Et[i].id);
         }else
         {
            int a=Tr.getpre(pl[Et[i].id]),b=Tr.getnext(pr[Et[i].id]);
            Tr.splay(a,root); Tr.splay(b,tr[root].rc);
            tr[tr[b].lc].ft=0; tr[b].lc=0;
         }
}

void bfs()
{
     int head=1,tail=2; q[head]=0;
     while(head<tail)
     {
           int u=q[head];
           for(int k=fst[u];k;k=pre[k]) q[tail++]=E[k];
           head++;
     }
}

void dp()
{
     for(int i=n+1;i>1;i--)
     {
         int u=q[i]; h[u]=0;
         for(int j=1;j<=K;j++) f[u][j]=g[u][j]=V[u];
         for(int k=fst[u];k;k=pre[k])
         {
             for(int j=1;j<K;j++)
                 h[u]=max(h[u],max(abs(f[E[k]][j]-g[u][K-j]),abs(g[E[k]][j]-f[u][K-j])));
             for(int j=2;j<K;j++)
             {
                 f[u][j]=min(f[u][j],f[E[k]][j-1]);
                 g[u][j]=max(g[u][j],g[E[k]][j-1]);
             }
         }
     }
     h[0]=0; int k=fst[0];
     for(int j=2;j<=K;j++) f[0][j]=f[E[k]][j-1],g[0][j]=g[E[k]][j-1];
     for(k=pre[k];k;k=pre[k])
     {
         for(int j=1;j<K-1;j++)
             h[0]=max(h[0],max(abs(f[E[k]][j]-g[0][K-j]),abs(g[E[k]][j]-f[0][K-j])));
         for(int j=2;j<K;j++)
         {
             f[0][j]=min(f[0][j],f[E[k]][j-1]);
             g[0][j]=max(g[0][j],g[E[k]][j-1]);
         }
     }
}

void work()
{
     build(); bfs(); dp();
     ans=0;
     for(int i=0;i<=n;i++) ans=max(ans,h[i]);
     printf("%d\n",ans);
}

int main()
{
    int TT=get();
    for(int i=1;i<=TT;i++)
    {
        printf("Case %d: ",i);
        init();
        work();
    }
    return 0;
}

  1. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.