Life is a Line

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)

Total Submission(s): 198 Accepted Submission(s): 76

Problem Description

There is a saying: Life is like a line, some people are your parallel lines, while others are destined to meet you.
Maybe have met, maybe just a matter of time, two unparallel lines will always meet in some places, and now a lot of life (i.e. line) are in the same coordinate system, in a given open interval, how many pairs can meet each other?

Input

There are several test cases in the input.

Each test case begin with one integer N (1 ≤ N ≤ 50000), indicating the number of different lines.
Then two floating numbers L, R follow (-10000.00 ≤ L < R ≤ 10000.00), indicating the interval (L, R).
Then N lines follow, each line contains four floating numbers x1, y1, x2, y2 (-10000.00 ≤ x1, y1, x2, y2 ≤ 10000.00), indicating two different points on the line. You can assume no two lines are the same one.

The input terminates by end of file marker.

Output

For each test case, output one integer, indicating pairs of intersected lines in the open interval, i.e. their intersection point’s x-axis is in (l, r).

Sample Input

3
0.0 1.0
0.0 0.0 1.0 1.0
0.0 2.0 1.0 2.0
0.0 2.5 2.5 0.0

Sample Output

Author

iSea @ WHU

Source

2010 ACM-ICPC Multi-University Training Contest（3）——Host by WHU

Recommend

zhouzeyong

/*
题意：给出你n条直线的两点，让你求出在l到r区间内的交点个数

初步思路：首先暴力肯定是行不通的，可以转化成在(l,r)区间内的线段相交问题，线段相交可以想想成是竖直方向上的覆盖面
    重叠问题，就是一条线段在(l,r)区间内的竖直方向的覆盖区域，如果两条线段的覆盖区域有重叠的那么这两条线段肯定是
    相交的，这样就转化成了求逆序对问题
    
    树状数组求逆序对，先将序对按照从小到大的循序排列，然后查找另一侧查找比他大的序对有多少
*/
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define exp 1e-6
#define lowbit(x) ( x&(-x) )
using namespace std;
struct Point{//点
    double x,y;
    int id;
    Point(){}
    Point(int a,int b){
      x=a;
      y=b;
    }
    void input(){//定义输入函数方便用的时候
      scanf("%lf%lf",&x,&y);
    }
};
vector<Point>v;//用来存放所有的线段（序对）
Point a,b;
double l,r;
int n;
int res=0;
int c[50010];
Point manage(Point a,Point b){//处理出来在竖直方向的覆盖线段
    Point cur;
    if(a.x!=b.x&&a.y==b.y){//水平方向的线段
        cur.x=a.y;
        cur.y=a.y;
        return cur;
    }
    double k=(b.y-a.y)/(b.x-a.x);
    double t=a.y-a.x*k;
    cur.x=k*l+t;
    cur.y=k*r+t;
    return cur;
}
bool cmp_1(Point a,Point b){
    if(a.x!=b.x)
        return a.x<b.x;
    return a.y<b.y;
}
bool cmp_2(Point a,Point b){
    if(a.y!=b.y)
        return a.y>b.y;
    return a.x>b.x;
}
void add(int x){
    while(x<50005){
        c[x]++;
        x+=lowbit(x);
    }
}
int getsum(int x){
    int res=0;
    while(x>0){
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}
void init(){
    v.clear();
    res=0;
    memset(c,0,sizeof c);
}
int main(){
    // freopen("in.txt","r",stdin);
    while(scanf("%d",&n)!=EOF){
        init();
        scanf("%lf%lf",&l,&r);
        //cout<<l<<" "<<r<<endl;
        for(int i=0;i<n;i++){
            a.input();
            b.input();
            if(a.x==b.x){//竖直方向上的线段
                if(a.x>l&&a.x<r)
                    res++;
                continue;
            }
            v.push_back(manage(a,b));
        }//处理输入
        // cout<<"ok"<<endl;
        //离散化坐标
        sort(v.begin(),v.end(),cmp_1);
        for(int i=0;i<v.size();i++){
            v[i].id=i+1;
        }
        // cout<<"ok"<<endl;
        int cur=0;
        sort(v.begin(),v.end(),cmp_2);
        for(int i=0;i<v.size();i++){
            add(v[i].id);
            //cout<<v[i].id<<" ";
            // cout<<"ok"<<endl;
            cur+=getsum(v[i].id-1);
            //cout<<i<<endl;
        }
        //cout<<endl;
        // for(int i=0;i<10;i++){
            // cout<<c[i]<<" ";
        // }
        printf("%d
",cur+res*v.size());
    }
    return 0;
}