Question

Problema #2103 de pe pbinfo
Cerința

 Se dau N segmente în plan, fiecare fiind paralel cu una dintre axele de coordonate.

 Determinați numărul total de puncte de intersecție între două segmente.

Answer 1

#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));

}