【POJ】1436 Horizontally Visible Segments

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<vector>
  4 #include<algorithm>
  5 #include<set>
  6 using namespace std;
  7 #define MAXN 16010
  8 #define INF 123456789
  9 struct Seg
 10 {
 11     int y1,y2,x;
 12     friend bool operator<(Seg a,Seg b)
 13     {
 14         return a.x<b.x;
 15     }
 16 };
 17 int i,tree[MAXN<<2];
 18 Seg p[MAXN];
 19 vector<int>G[MAXN];
 20 vector<int>::iterator it;
 21 inline void PushDown(int rt)
 22 {
 23     if(tree[rt])
 24     {
 25         tree[rt<<1]=tree[rt<<1|1]=tree[rt];
 26         tree[rt]=0;
 27     }
 28 }
 29 void Update(int x,int y,int val,int L,int R,int rt)
 30 {
 31     if(x<=L&&R<=y)
 32         tree[rt]=val;
 33     else
 34     {
 35         int mid=(L+R)>>1;
 36         PushDown(rt);
 37         if(x<=mid)
 38             Update(x,y,val,L,mid,rt<<1);
 39         if(y>mid)
 40             Update(x,y,val,mid+1,R,rt<<1|1);
 41     }
 42 }
 43 void Query(int x,int y,int L,int R,int rt)
 44 {
 45     if(x<=L&&R<=y)
 46     {
 47         if(tree[rt])
 48         {
 49             G[i].push_back(tree[rt]);
 50             G[tree[rt]].push_back(i);
 51         }
 52         else if(L!=R)
 53         {
 54             int mid=(L+R)>>1;
 55             Query(x,y,L,mid,rt<<1);
 56             Query(x,y,mid+1,R,rt<<1|1);
 57         }
 58     }
 59     else
 60     {
 61         int mid=(L+R)>>1;
 62         PushDown(rt);
 63         if(x<=mid)
 64             Query(x,y,L,mid,rt<<1);
 65         if(y>mid)
 66             Query(x,y,mid+1,R,rt<<1|1);
 67     }
 68 }
 69 int main()
 70 {
 71     int t,n,j,k,r,left,right,ans;
 72     scanf("%d",&t);
 73     while(t--)
 74     {
 75         left=INF;
 76         ans=right=0;
 77         scanf("%d",&n);
 78         for(i=1;i<=n;i++)
 79         {
 80             scanf("%d%d%d",&p[i].y1,&p[i].y2,&p[i].x);
 81             p[i].y1<<=1;
 82             p[i].y2<<=1;
 83             left=min(left,p[i].y1);
 84             right=max(right,p[i].y2);
 85             G[i].clear();
 86         }
 87         sort(p+1,p+1+n);
 88         memset(tree,0,sizeof(tree));
 89         for(i=1;i<=n;i++)
 90         {
 91             Query(p[i].y1,p[i].y2,left,right,1);
 92             Update(p[i].y1,p[i].y2,i,left,right,1);
 93         }
 94         for(i=1;i<=n;i++)
 95         {
 96             sort(G[i].begin(),G[i].end());
 97             it=unique(G[i].begin(),G[i].end());
 98             G[i].resize(it-G[i].begin());
 99         }
100         for(i=1;i<=n;i++)
101         {
102             for(j=0;j<G[i].size();j++)
103             {
104                 for(k=j+1;k<G[i].size();k++)
105                 {
106                     r=lower_bound(G[G[i][j]].begin(),G[G[i][j]].end(),G[i][k])-G[G[i][j]].begin();
107                     if(r<G[G[i][j]].size()&&G[G[i][j]][r]==G[i][k])
108                         ans++;
109                 }
110             }
111         }
112         printf("%d\n",ans/3);
113     }
114     return 0;
115 }
新博客：www.zhixiangli.com