HDU 5862 Counting Intersections 扫描线+树状数组Counting Intersections

题目链接：

http://acm.split.hdu.edu.cn/showproblem.php?pid=5862

Counting Intersections

Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

问题描述

Given some segments which are paralleled to the coordinate axis. You need to count the number of their intersection.

The input data guarantee that no two segments share the same endpoint, no covered segments, and no segments with length 0.

输入

The first line contains an integer T, indicates the number of test case.

The first line of each test case contains a number n(1<=n<=100000), the number of segments. Next n lines, each with for integers, x1, y1, x2, y2, means the two endpoints of a segment. The absolute value of the coordinate is no larger than 1e9.

输出

For each test case, output one line, the number of intersection.

样例

sample input
2
4
1 0 1 3
2 0 2 3
0 1 3 1
0 2 3 2
4
0 0 2 0
3 0 3 2
3 3 1 3
0 3 0 2

sample output
4
0

题意

给你若干个平行于坐标轴的，长度大于0的线段，且任意两个线段没有公共点，不会重合覆盖。问有多少个交点。

题解

扫描线+树状数组
首先把平行于x轴的线段和平行于y轴的线段分开存。对于平行于y轴的线段，我们按它的上端点排降序，对于平行于x轴的线段，我们按照它们的高度排降序。

然后我们遍历一遍平行于x轴的线段，考虑有多少条线段与当前遍历的平行于x轴的线段所在的直线相交的线段，并且更新到树状数组中，那么与当前平行于x轴的线段相交的垂直线段为sum(r)-sum(l-1),l、r分别为当前线段的左右端点。

那么，如何维护与某条直线相交的垂直线段呢？
由于我们遍历平行于x轴的直线是按高度从高到低的，对于上端点高于当前遍历高度的所有垂直线段都压到树状数组中，并且把它们的下端点（大的优先）压到优先队列中，然后再从优先队列中踢掉下端点大于当前遍历高度的，同时更新树状数组（删除操作）。

由于数据范围比较大，横坐标需要离散化。

代码

#include<map>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define X first
#define Y second
#define mkp make_pair
#define lson (o<<1)
#define rson ((o<<1)|1)
#define mid (l+(r-l)/2)
#define sz() size()
#define pb(v) push_back(v)
#define all(o) (o).begin(),(o).end()
#define clr(a,v) memset(a,v,sizeof(a))
#define bug(a) ;//cout<<#a<<" = "<<a<<endl
#define rep(i,a,b) for(int i=a;i<(b);i++)
#define reu(i,a,b) for(int i=a;i<=(b);i++)

typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<pair<int,int> > VPII;

const int INF=0x3f3f3f3f;
const LL INFL=0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-8;

//start----------------------------------------------------------------------

const int maxn=4e5+10;

LL sumv[maxn];

struct Node{
    int val,u,v;
    Node(int val,int u,int v):val(val),u(u),v(v){}
    bool operator < (const Node& tmp) const {
        return val>tmp.val;
    }
};

bool cmp(const Node& n1,const Node& n2){
    return n1.v>n2.v;
}

LL sum(int x){
    LL ret=0;
    while(x>0){
        ret+=sumv[x];
        x-=(x&-x);
    } 
    return ret;
}

void add(int x,int v){
    while(x<maxn){
        sumv[x]+=v;
        x+=(x&-x);
    }
}

VI ha; 
vector<Node> col,row;
int n;

void init(){
    ha.clear();
    col.clear();
    row.clear();
    clr(sumv,0);
}

int main() {
    int tc;
    scanf("%d",&tc);
    while(tc--){
        
        scanf("%d",&n);
        init();
        
        rep(i,0,n){
            int u1,v1,u2,v2;
            scanf("%d%d%d%d",&u1,&v1,&u2,&v2);
            if(u1==u2){
                if(v1>v2) swap(v1,v2);
                col.push_back(Node(u1,v1,v2));
            }else{
                if(u1>u2) swap(u1,u2);
                row.push_back(Node(v1,u1,u2));
            }
            ha.push_back(u1);
            ha.push_back(u2);
        }
        
        sort(all(ha));
        ha.erase(unique(all(ha)),ha.end());
        
        sort(all(col),cmp);
        sort(all(row));
        
        priority_queue<pair<int,int> > pq;
        int p=0;
        LL ans=0;
        rep(i,0,row.sz()){
            int hi=row[i].val;
            bug(hi);
            while(p<col.sz()&&col[p].v>=hi){
                int id=lower_bound(all(ha),col[p].val)-ha.begin()+1;
                pq.push(mkp(col[p].u,id));
                add(id,1);
                p++;
            }
            while(!pq.empty()&&pq.top().X>hi){
                add(pq.top().Y,-1);
                pq.pop();
            }
            int l=lower_bound(all(ha),row[i].u)-ha.begin()+1;
            int r=lower_bound(all(ha),row[i].v)-ha.begin()+1;
            ans+=sum(r)-sum(l-1); 
        }
        
        printf("%lldn",ans);
    }
    return 0;
}

//end-----------------------------------------------------------------------

/*
4
1 0 1 1
0 1 2 1
3 1 3 2
1 2 1 3
*/