ZOJ – 3157：Weapon （几何 逆序对）

pro：给定平面上N条直线，保证没有直线和Y轴平行。 求有多少交点的X坐标落在(L,R)开区间之间，注意在x=L或者R处的不算。

sol：求出每条直线与L和R的交点，如果A直线和B直线在（L，R）相交，一定有Xa<Xb而且Ya>Yb（或相反）；那么即是求逆序对。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pdd pair<double,double>
#define ll long long
using namespace std;
const int maxn=;
struct point{
    double x,y;
    point(){}
    point(double xx,double yy):x(xx),y(yy){}
}s[maxn];
struct line{
    point s,p;
    line(){}
    line(point xx,point yy):s(xx),p(yy){}
};
point operator *(double t,point a){ return point(t*a.x,t*a.y);}
point operator -(point w,point v){return point(w.x-v.x,w.y-v.y);}
point operator +(point w,point v){return point(w.x+v.x,w.y+v.y);}
double det(point w,point v){ return w.x*v.y-w.y*v.x;}
double dot(point w,point v){ return w.x*v.x+w.y*v.y;}
point inters(line a,line b){
    point p=a.s-b.s;
    double t=det(b.p,p)/det(a.p,b.p);
    return a.s+t*a.p;
}
int sum[maxn],b[maxn],N; double L,R,a[maxn];
point A[maxn],B[maxn]; ll ans;
line F,C;
struct in{
    double a,b; int id;
    bool friend operator<(in w,in v){
        if(w.a==v.a) return w.b<v.b;
        return w.a<v.a;
    }
}fcy[maxn],ys[maxn];
void add(int x){
    while(x<=N) {
        sum[x]++;
        x+=(-x)&x;
    }
}
int query(int x){
    int res=; while(x){
        res+=sum[x];
        x-=(-x)&x;
    }
    return res;
}
int main()
{
    while(~scanf("%d",&N)&&N){
        rep(i,,N)
          scanf("%lf%lf%lf%lf",&A[i].x,&A[i].y,&B[i].x,&B[i].y);
        scanf("%lf%lf",&L,&R);
        F=line(point(L,0.0),point(.,1.0));
        C=line(point(R,0.0),point(.,1.0));
        rep(i,,N) {
            point tA=A[i],tB=B[i];
            A[i]=inters(line(tA,tB-tA),F);
            B[i]=inters(line(tA,tB-tA),C);
        }
        rep(i,,N) fcy[i].a=A[i].y,fcy[i].b=B[i].y;        sort(fcy+,fcy+N+);
        rep(i,,N) ys[i].a=fcy[i].b,ys[i].id=i;
        sort(ys+,ys+N+);
        rep(i,,N) a[i]=ys[i].a;
        rep(i,,N) b[ys[i].id]=lower_bound(a+,a+N+,ys[i].a)-a;
        ans=;
        rep(i,,N) sum[i]=;
        for(int i=N;i>=;i--){
            ans+=query(b[i]-);
            add(b[i]);
        }
        printf("%lld\n",ans);
    }
    return ;
}