HDU 5862Counting Intersections

Counting Intersections

Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 51 Accepted Submission(s): 18

Problem Description

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.

Input

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.

Output

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

Sample Input

1 0 1 3

2 0 2 3

0 1 3 1

0 2 3 2

0 0 2 0

3 0 3 2

3 3 1 3

0 3 0 2

Sample Output

对于横着的线，遇到左端点+1 遇到右端点-1 遇到竖着的线求和。

/* ***********************************************
Author        :guanjun
Created Time  :2016/8/18 14:20:26
File Name     :p1006.cpp
************************************************ */
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <iomanip>
#include <list>
#include <deque>
#include <stack>
#define ull unsigned long long
#define ll long long
#define mod 90001
#define INF 0x3f3f3f3f
#define maxn 100010
#define cle(a) memset(a,0,sizeof(a))
const ull inf = 1LL << 61;
const double eps=1e-5;
using namespace std;
priority_queue<int,vector<int>,greater<int> >pq;
struct node{
    int type,x,y,y2;
}nod[maxn*2];
int a[maxn*2];
int Maxn;
bool cmp(node a,node b){
    if(a.x==b.x)return a.type<b.type;
    return a.x<b.x;
}
int c[maxn*2];
int lowbit(int i){
    return i&(-i);
}
void add(int i,int d){
    while(i<=Maxn){
        c[i]+=d;
        i+=lowbit(i);
    }
}
int sum(int i){
    int ans=0;
    while(i>0){
        ans+=c[i];
        i-=lowbit(i);
    }
    return ans;
}
map<int,int>mp;
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    //freopen("out.txt","w",stdout);
    int t;
    scanf("%d",&t);
    while(t--){
        mp.clear();
        int n,tot=0;
        int all=1;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            int x1,x2,y1,y2;
            scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
            if(x1==x2){
                if(y1>y2)swap(y1,y2);
                nod[tot++]={1,x1,y1,y2};
                a[all++]=y1;
                a[all++]=y2;
            }
            else{
                if(x1>x2)swap(x1,x2);
                nod[tot++]={0,x1,y1,1};
                nod[tot++]={0,x2+1,y2,-1};
                a[all++]=y1;
            }
        }
        sort(a+1,a+all);
        int cnt=0;
        for(int i=1;i<=all;i++){
            if(!mp[a[i]])mp[a[i]]=++cnt;
        }
        Maxn=cnt+1;
        sort(nod,nod+tot,cmp);
        ll ans=0;
        cle(c);
        for(int i=0;i<tot;i++){
            if(nod[i].type==0){
                int xpy=mp[nod[i].y];
                add(xpy,nod[i].y2);
            }
            else{
                int xpl=mp[nod[i].y];
                int xpr=mp[nod[i].y2];
                ans+=sum(xpr)-sum(xpl-1);
            }
        }
        printf("%lld
",ans);
    }
    return 0;
}