Hdu 5862 Counting Intersections(有n条线段,每一条线段都是平行于x轴或者y轴,问有多少个交点)

71 阅读 0 评论 47 点赞

我是靠谱客的博主文静小熊猫，最近开发中收集的这篇文章主要介绍Hdu 5862 Counting Intersections(有n条线段,每一条线段都是平行于x轴或者y轴,问有多少个交点)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

传送门:Hdu 5862 Counting Intersections

题意:有n条线段,每一条线段都是平行于x轴或者y轴,问有多少个交点

思路:按x排序,只统计竖直的与水平相交的情况,
比如竖直的(x1,y1)-(x1,y2),就是统计sum(y2)-sum(y1-1)
水平的:(x1,y1),(x2,y1),就是在x1这个位置add(y1,1),在x2这个位置add(y1,-1)

#include<bits/stdc++.h>
using namespace std;
const int maxn=2*100010;
int t[maxn];
struct node{
    int x,l,r,flag;
}e[maxn];
int C[maxn],m;

bool cmp(node u,node v){
    if(u.x==v.x)
        return u.flag>v.flag;
    return u.x<v.x;
}

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

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

int main(){
    int _,n;
    scanf("%d",&_);
    while(_--){
        scanf("%d",&n);
        int x1,y1,x2,y2,Count=0;
        m=0;
        for(int i=1;i<=n;i++){
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            if(x1>x2)
                swap(x1,x2);
            if(y1>y2)
                swap(y1,y2);
            t[++m]=y1,t[++m]=y2;
            if(x1==x2)//竖直
                e[++Count]=(node){x1,y1,y2,0};
            else{
                e[++Count]=(node){x1,y1,y2,1};
                e[++Count]=(node){x2,y1,y2,-1};
            }
        }
        sort(t+1,t+m+1);
        m=unique(t+1,t+m+1)-t-1;
        sort(e+1,e+Count+1,cmp);
        for(int i=1;i<=m;i++)
            C[i]=0;
        long long ans=0;
        for(int i=1;i<=Count;i++){
            if(e[i].flag==0){
                int l=lower_bound(t+1,t+m+1,e[i].l)-t-1,r=lower_bound(t+1,t+m+1,e[i].r)-t;
                ans+=sum(r)-sum(l);
            }
            else{
                int num=lower_bound(t+1,t+m+1,e[i].l)-t;
                add(num,e[i].flag);
            }
        }
        printf("%lldn",ans);
    }
    return 0;
}