Intersectie Segmente

#include <fstream>
#include <algorithm>
#define NMAX 200010
#define CMAX 300010

using namespace std;

FILE *fin, *fout;

struct segment
{
    int x, y1, y2, tip;
};

int n, nr, ain[4 * CMAX], sol, ymax, aib[CMAX];
segment A[NMAX];

bool crit(segment a, segment b);
void update(int x, int q, int st, int dr, int nod);
int calcul(int a, int b, int st, int dr, int nod);
void update(int x, int q);
int calcul(int x);
int zeros(int x);

int main()
{
    int i, x1, y1, x2, y2;
    fin = fopen("is.in", "r");
    fout = fopen("is.out", "w");
    fscanf(fin, "%d", &n);
    for (i = 1; i <= n; i++)
    {
        fscanf(fin, "%d%d%d%d", &x1, &y1, &x2, &y2);
        if (y1 == y2)
        {
            A[++nr].x = x1;
            A[nr].tip = 1;
            A[nr].y1 = y1;
            A[++nr].x = x2;
            A[nr].tip = -1;
            A[nr].y1 = y1;
        }
        else
        {
            A[++nr].x = x1;
            A[nr].tip = 0;
            A[nr].y1 = y1;
            A[nr].y2 = y2;
        }
        if (y2 > ymax)
            ymax = y2;
    }
    sort(A + 1, A + nr + 1, crit);
    if (ymax <= 100000)
    {
        for (i = 1; i <= nr; i++)
        {
            if (A[i].tip == 0)
                sol += calcul(A[i].y1, A[i].y2, 0, 100010, 1);
            else
                update(A[i].y1, A[i].tip, 0, 100010, 1);
        }
    }
    else
    {
        for (i = 1; i <= nr; i++)
        {
            if (A[i].tip == 0)
                sol += calcul(A[i].y2) - calcul(A[i].y1 - 1);
            else
                update(A[i].y1, A[i].tip);
        }
    }
    fprintf(fout, "%d\n", sol);
    fclose(fout);
    return 0;
}

bool crit(segment a, segment b)
{
    return a.x < b.x;
}
void update(int x, int q, int st, int dr, int nod)
{
    int mij = ((st + dr) >> 1);
    ain[nod] += q;
    if (st == dr)
        return ;
    if (x <= mij)
        update(x, q, st, mij, nod << 1);
    else
        update(x, q, mij + 1, dr, (nod << 1) + 1);
}
int calcul(int a, int b, int st, int dr, int nod)
{
    int rez = 0, mij = ((st + dr) >> 1);
    if (st >= a && dr <= b)
        return ain[nod];
    if (a <= mij)
        rez += calcul(a, b, st, mij, nod << 1);
    if (b > mij)
        rez += calcul(a, b, mij + 1, dr, (nod << 1) + 1);
    return rez;
}
void update(int x, int q)
{
    int i;
    for (i = x; i <= ymax; i += zeros(i))
        aib[i] += q;
}
int calcul(int x)
{
    int i, rez = 0;
    for (i = x; i > 0; i -= zeros(i))
        rez += aib[i];
    return rez;
}
int zeros(int x)
{
    return (x & (-x));
}