HDU - 5862 Counting Intersections

59 阅读 0 评论 39 点赞

我是靠谱客的博主落后酸奶，最近开发中收集的这篇文章主要介绍HDU - 5862 Counting Intersections，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1.题面

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

2.题意

给你n条与与坐标轴平行的线段，求这些线段总共有多少交点

3.思路

可以看成是算法导论中BO算法的一个特例，　解决问题的思路上有一点像，

但这道题的思路更简单，　将纵坐标离散化，　然后blablabla．．．．．．

4.代码

/*****************************************************************
    > File Name: err.cpp
    > Author: Uncle_Sugar
    > Mail: uncle_sugar@qq.com
    > Created Time: Thu 18 Aug 2016 15:24:27 CST
*****************************************************************/
# include <cstdio>
# include <cstring>
# include <cctype>
# include <cmath>
# include <cstdlib>
# include <climits>
# include <iostream>
# include <iomanip>
# include <set>
# include <map>
# include <vector>
# include <stack>
# include <queue>
# include <algorithm>
using namespace std;

# define rep(i,a,b) for (i=a;i<=b;i++)
# define rrep(i,a,b) for (i=b;i>=a;i--)

template<class T>void PrintArray(T* first,T* last,char delim=' '){
    for (;first!=last;first++) cout << *first << (first+1==last?'n':delim);
}

const int debug = 1;
const int size  = 10 + 100000; 
const int INF = INT_MAX>>1;
typedef long long ll;

/*
1.see the size of the input data before you select your algorithm 
2.cin&cout is not recommended in ACM/ICPC
3.pay attention to the size you defined, for instance the size of edge is double the size of vertex
*/

struct Line{
    int lb, ub;
    int other;
}line[size];

int yset[size*4], ylen;

int hhash(int y){
    return lower_bound(yset + 1, yset + ylen + 1, y) - (yset);
}

int BIT[size*4];

inline int lowbit(int x){return x&(-x);}

int Sum(int pos){
    int ret = 0;
    while (pos > 0){
        ret += BIT[pos];        
        pos -= lowbit(pos);
    }
    return ret;
}

int Add(int pos, int val){
    while (pos <= ylen + 1){
        BIT[pos] += val;    
        pos += lowbit(pos);
    }
}

struct Point{
    int x;
    int index;
    int type; /*zuo 1 shu 2 you 3*/
    bool operator < (const Point& cmper)const{
        if (x != cmper.x)
            return x < cmper.x;
        return type < cmper.type;
    }
    //# void Print(){
        //# cout << "x index type " << x << " " << index << " " << type << endl;
    //# }
}point[size*4];
int plen;

int main()
{
    /*std::ios::sync_with_stdio(false);cin.tie(0);*/
    int i,j;
    int T;
    scanf("%d", &T);
    while (T--){
        ylen = 1;
        plen = 0;
        memset(BIT, 0, sizeof(BIT));
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n; i++){
            int x1,y1,x2,y2;
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            if (x1 == x2){

                if (y1 > y2) swap(y1, y2);
                line[i].lb = y1; 
                line[i].ub = y2;
                line[i].other = x1;

                yset[ylen++] = y1;
                yset[ylen++] = y2;

                point[plen].x = x1;            
                point[plen].index = i;
                point[plen].type = 2;
                plen++;

            }else if (y1 == y2){

                if (x1 > x2) swap(x1, x2);
                line[i].lb = x1;
                line[i].ub = x2;
                line[i].other = y1;

                yset[ylen++] = y1;

                point[plen].x = x1;            
                point[plen].index = i;
                point[plen].type = 1;
                plen++;

                point[plen].x = x2;            
                point[plen].index = i;
                point[plen].type = 3;
                plen++;
            }
        }

        sort(yset + 1, yset + ylen + 1);
        ylen = unique(yset + 1, yset + ylen + 1) - (yset + 1) ;
        
        sort(point, point + plen);

        ll ans = 0;
        for (int i = 0; i < plen; i++){
            if (point[i].type == 1){
                Add(hhash(line[point[i].index].other), 1);
            }else if (point[i].type == 3){
                Add(hhash(line[point[i].index].other), -1);
            }else if (point[i].type == 2){
                int k = point[i].index;    
                int uy = line[k].ub;
                int ly = line[k].lb;
                ans += Sum(hhash(uy)) - Sum(hhash(ly)-1); 
            }
        }
        printf("%lldn",ans);
    }
    return 0;
}