POJ 1436 区间染色

Horizontally Visible Segments

Time Limit: 5000MS		Memory Limit: 65536K
Total Submissions: 4507		Accepted: 1662

Description

There is a number of disjoint vertical line segments in the plane. We say that two segments are horizontally visible if they can be connected by a horizontal line segment that does not have any common points with other vertical segments. Three different vertical segments are said to form a triangle of segments if each two of them are horizontally visible. How many triangles can be found in a given set of vertical segments?

Task

Write a program which for each data set:

reads the description of a set of vertical segments,

computes the number of triangles in this set,

writes the result.

Input

The first line of the input contains exactly one positive integer d equal to the number of data sets, 1 <= d <= 20. The data sets follow.

The first line of each data set contains exactly one integer n, 1 <= n <= 8 000, equal to the number of vertical line segments.

Each of the following n lines consists of exactly 3 nonnegative integers separated by single spaces:

yi', yi'', xi - y-coordinate of the beginning of a segment, y-coordinate of its end and its x-coordinate, respectively. The coordinates satisfy 0 <= yi' < yi'' <= 8 000, 0 <= xi <= 8 000. The segments are disjoint.

Output

The output should consist of exactly d lines, one line for each data set. Line i should contain exactly one integer equal to the number of triangles in the i-th data set.

Sample Input

Sample Output

Source

Central Europe 2001

题目意思：

给n条垂直x轴的线段，若两个线段之间存在没有其他线段挡着的地方，则称两个线段为可见的。若3条线段两两互为可见，称为一组，求n条线段中有多少组。

思路：

很明显线段树，按x坐标排序，以y建线段树，每加入一条边就和之前的颜色用visited标记起来，然后暴力三重循环即可（虽然一重循环是8000，但是实际上没这么多）。

注意，插入边的时候，边的两端点*2再插入，还是边界问题。

代码：

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <iostream>
  5 #include <vector>
  6 #include <queue>
  7 #include <cmath>
  8 #include <set>
  9 using namespace std;
 10 
 11 #define N 10005
 12 #define ll root<<1
 13 #define rr root<<1|1
 14 #define mid (a[root].l+a[root].r)/2
 15 
 16 
 17 int max(int x,int y){return x>y?x:y;}
 18 int min(int x,int y){return x<y?x:y;}
 19 int abs(int x,int y){return x<0?-x:x;}
 20 
 21 struct Line{
 22     int y1, y2, x;
 23 }line[N];
 24 
 25 struct node{
 26     int l, r, val;
 27     bool f;
 28 }a[N*8];
 29 
 30 int n;
 31 bool visited[8002][8002];
 32 
 33 bool cmp(Line a,Line b){
 34     return a.x<b.x;
 35 }
 36 
 37 void build(int l,int r,int root){
 38     a[root].l=l;
 39     a[root].r=r;
 40     a[root].val=0;
 41     a[root].f=false;
 42     if(l==r) return;
 43     build(l,mid,ll);
 44     build(mid+1,r,rr);
 45 }
 46 
 47 void down(int root){
 48     if(a[root].f&&a[root].val>0&&a[root].l!=a[root].r){
 49         a[ll].val=a[rr].val=a[root].val;
 50         a[root].val=-1;
 51         a[ll].f=a[rr].f=true;
 52     }
 53 }
 54 void update(int l,int r,int val,int root){
 55     //if(!a[root].f) a[root].f=true;
 56     if(a[root].val==val) return;
 57     if(a[root].l==l&&a[root].r==r){
 58         if(!a[root].f){
 59             a[root].f=true;
 60             a[root].val=val;
 61             return;
 62         }
 63         else{
 64             if(a[root].val>0){
 65                 if(!visited[a[root].val][val]){
 66                     visited[a[root].val][val]=visited[val][a[root].val]=true;
 67                 }
 68                 a[root].val=val;
 69                 return;
 70             }
 71         }
 72     }
 73     down(root);
 74     if(r<=a[ll].r) update(l,r,val,ll);
 75     else if(l>=a[rr].l) update(l,r,val,rr);
 76     else{
 77         update(l,mid,val,ll);
 78         update(mid+1,r,val,rr);
 79     }
 80     if(a[ll].f||a[rr].f) a[root].f=true;
 81     if(a[ll].val==a[rr].val&&a[ll].val>0) a[root].val=a[ll].val;
 82 }
 83 
 84 void out(int root){
 85     if(a[root].l==a[root].r) {
 86         printf("%d ",a[root].val);return;
 87     }
 88     down(root);
 89     out(ll);
 90     out(rr);
 91 }
 92 main()
 93 {
 94     int t, i, j, k;
 95     cin>>t;
 96     while(t--){
 97         scanf("%d",&n);
 98         int minh=999999999, maxh=-1;
 99         for(i=0;i<n;i++){
100             scanf("%d %d %d",&line[i].y1,&line[i].y2,&line[i].x);
101             minh=min(min(line[i].y1,line[i].y2),minh);
102             maxh=max(max(line[i].y1,line[i].y2),maxh);
103         } 
104         build(minh*2,maxh*2,1);
105         sort(line,line+n,cmp);
106         memset(visited,false,sizeof(visited));
107         for(i=0;i<n;i++) update(line[i].y1*2,line[i].y2*2,i+1,1);//,out(1),cout<<endl;
108         int ans=0;
109         
110         for(i=1;i<=n;i++){
111             for(j=i+1;j<=n;j++){
112                 if(visited[i][j]){
113                     for(k=j+1;k<=n;k++){
114                         if(visited[j][k]&&visited[i][k]){
115                             ans++;
116                         }
117                     }
118                 }
119             }
120         }
121         printf("%d
",ans);
122         
123     }
124 }