Intersectie Segmente

#include <fstream>
#include <cstdlib>
using namespace std;
struct entry
{
    int x,y1,y2,sgn;
} A[200000];
typedef struct entry entry;
int N,T[1000000];
long long Res;

int cmp(const void *i,const void *j)
{
   entry *ei=(entry *)i,*ej=(entry *)j;

    if(ei->x!=ej->x)
       return ei->x-ej->x;
    return ej->sgn-ei->sgn;
}

int query(int n,int l,int r,int a,int b)
{
    int m,t=0;

   if(a<=l&&r<=b)
       return T[n];
   else
   {
    m=(l+r)/2;
    if(a<=m)
     t+=query(2*n,l,m,a,b);
    if(b>m)
     t+=query(2*n+1,m+1,r,a,b);
    }
    return t;
}

void update(int n,int l,int r,int p,int v)
{
    int m=(l+r)/2;

    T[n]+=v;
    if(l==r) return;
    if(p<=m)
       update(2*n,l,m,p,v);
    else
       update(2*n+1,m+1,r,p,v);
}

int main(void)
{
    int i,n,x1,y1,x2,y2;
    ifstream f("is.in");
    f>>N;
    for(n=i=0;i<N;++i)
    {
     f>>x1>>y1>>x2>>y2;
      if(y1==y2)
        A[n].x=x1,A[n].sgn=+1,
        A[n++].y1=y1,
        A[n].x=x2,A[n].sgn=-1,
        A[n++].y1=y1;
      else
        if(x1==x2)
         A[n].x=x1,A[n].sgn=0,
         A[n].y1=y1,A[n++].y2=y2;
    }
    f.close();
    qsort(A,n,sizeof(entry),cmp);
    for (i=0;i<n;++i)
    if(A[i].sgn==0)
       Res+=query(1,0,99999,A[i].y1,A[i].y2);
    else
       update(1,0,99999,A[i].y1,A[i].sgn);
    ofstream g("is.out");
    g<<Res;
    g.close();
    return 0; }