HDU-5862-Counting Intersections（树状数组+离散化+扫描线）

130 阅读 0 评论 86 点赞

我是靠谱客的博主负责嚓茶，最近开发中收集的这篇文章主要介绍HDU-5862-Counting Intersections（树状数组+离散化+扫描线），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

题意：给出与坐标轴平行的线段，求所有线段的交点个数

题解：先将数据离散化，将两类线段分开存放；考虑横向线段的左右端点，将y值计数，只需将竖向线段扫描一遍，统计y1与y2之间的线段个数，维护bit就好。

CODE：

#include <bits/stdc++.h>
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long
#define bug cout<<"bug"<<endl
const int MAXN = 500007;
const int MOD = 1e9 + 9;
struct Line
{
    int x1,x2,y1,y2;
} line[MAXN],l[MAXN];
struct Node
{
    int x,y,flag;
} v[MAXN];
bool cmp1(Line a, Line b)
{
   return a.x1 < b.x1;
}
bool cmp2(Node a, Node b)
{
    if(a.x!=b.x)return a.x<b.x;
    return a.flag<b.flag;
}
int n;
vector<int> p;
long long sum[MAXN];
void add(int i, int x)
{
    while(i<=MAXN)
    {
        sum[i]+=x;
        i+=i&-i;
    }
}
long long get_sum(int i)
{
    long long ans=0;
    while(i>0)
    {
        ans+=sum[i];
        i-=i&-i;
    }
    return ans;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        p.clear();
        int x1,x2,y1,y2;
        scanf("%d",&n);
        int cnt1=0,cnt2=0;
        for(int i=0; i<n; ++i)
        {
            scanf("%d%d%d%d",&line[i].x1,&line[i].y1,&line[i].x2,&line[i].y2);
            if(line[i].x1>line[i].x2)swap(line[i].x1,line[i].x2);
            if(line[i].y1>line[i].y2)swap(line[i].y1,line[i].y2);
            p.push_back(line[i].x1);
            p.push_back(line[i].x2);
            p.push_back(line[i].y1);
            p.push_back(line[i].y2);
        }
        sort(p.begin(),p.end());
        p.resize(unique(p.begin(),p.end())-p.begin());
        for(int i=0; i<n; ++i)
        {
            x1=lower_bound(p.begin(),p.end(),line[i].x1)-p.begin()+1;
            x2=lower_bound(p.begin(),p.end(),line[i].x2)-p.begin()+1;
            y1=lower_bound(p.begin(),p.end(),line[i].y1)-p.begin()+1;
            y2=lower_bound(p.begin(),p.end(),line[i].y2)-p.begin()+1;
            if(x1==x2)l[cnt1++]=Line{x1,x2,y1,y2};
            else
            {
                v[cnt2].flag=0;
                v[cnt2].x=x1;
                v[cnt2++].y=y1;
                v[cnt2].flag=1;
                v[cnt2].x=x2;
                v[cnt2++].y=y2;
            }
        }
        memset(sum,0,sizeof(sum));
        sort(l,l+cnt1,cmp1);
        sort(v,v+cnt2,cmp2);
        long long ans=0;
        for(int i=0,j=0; i<cnt1; ++i)
        {
            while(j<cnt2 && (v[j].x<l[i].x1 ||(v[j].x==l[i].x1 && v[j].flag==0)))
            {
                if(v[j].flag==0)add(v[j].y,1);
                else add(v[j].y,-1);
                j++;
            }
            ans+=get_sum(l[i].y2)-get_sum(l[i].y1-1);
        }
        printf("%I64dn",ans);
    }
    return 0;
}
/*
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
*/