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
1
5
0 4 4
0 3 1
3 4 2
0 2 2
0 2 3
Sample Output
1
Source
题目意思：
给n条垂直x轴的线段，若两个线段之间存在没有其他线段挡着的地方，则称两个线段为可见的。若3条线段两两互为可见，称为一组，求n条线段中有多少组。
思路：
很明显线段树，按x坐标排序，以y建线段树，每加入一条边就和之前的颜色用visited标记起来，然后暴力三重循环即可（虽然一重循环是8000，但是实际上没这么多）。
注意，插入边的时候，边的两端点*2再插入，还是边界问题。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
using namespace std; #define N 10005
#define ll root<<1
#define rr root<<1|1
#define mid (a[root].l+a[root].r)/2 int max(int x,int y){return x>y?x:y;}
int min(int x,int y){return x<y?x:y;}
int abs(int x,int y){return x<?-x:x;} struct Line{
int y1, y2, x;
}line[N]; struct node{
int l, r, val;
bool f;
}a[N*]; int n;
bool visited[][]; bool cmp(Line a,Line b){
return a.x<b.x;
} void build(int l,int r,int root){
a[root].l=l;
a[root].r=r;
a[root].val=;
a[root].f=false;
if(l==r) return;
build(l,mid,ll);
build(mid+,r,rr);
} void down(int root){
if(a[root].f&&a[root].val>&&a[root].l!=a[root].r){
a[ll].val=a[rr].val=a[root].val;
a[root].val=-;
a[ll].f=a[rr].f=true;
}
}
void update(int l,int r,int val,int root){
//if(!a[root].f) a[root].f=true;
if(a[root].val==val) return;
if(a[root].l==l&&a[root].r==r){
if(!a[root].f){
a[root].f=true;
a[root].val=val;
return;
}
else{
if(a[root].val>){
if(!visited[a[root].val][val]){
visited[a[root].val][val]=visited[val][a[root].val]=true;
}
a[root].val=val;
return;
}
}
}
down(root);
if(r<=a[ll].r) update(l,r,val,ll);
else if(l>=a[rr].l) update(l,r,val,rr);
else{
update(l,mid,val,ll);
update(mid+,r,val,rr);
}
if(a[ll].f||a[rr].f) a[root].f=true;
if(a[ll].val==a[rr].val&&a[ll].val>) a[root].val=a[ll].val;
} void out(int root){
if(a[root].l==a[root].r) {
printf("%d ",a[root].val);return;
}
down(root);
out(ll);
out(rr);
}
main()
{
int t, i, j, k;
cin>>t;
while(t--){
scanf("%d",&n);
int minh=, maxh=-;
for(i=;i<n;i++){
scanf("%d %d %d",&line[i].y1,&line[i].y2,&line[i].x);
minh=min(min(line[i].y1,line[i].y2),minh);
maxh=max(max(line[i].y1,line[i].y2),maxh);
}
build(minh*,maxh*,);
sort(line,line+n,cmp);
memset(visited,false,sizeof(visited));
for(i=;i<n;i++) update(line[i].y1*,line[i].y2*,i+,);//,out(1),cout<<endl;
int ans=; for(i=;i<=n;i++){
for(j=i+;j<=n;j++){
if(visited[i][j]){
for(k=j+;k<=n;k++){
if(visited[j][k]&&visited[i][k]){
ans++;
}
}
}
}
}
printf("%d\n",ans); }
}