Cod sursa(job #2325420)

Utilizator cosceexcosceex cosceex Data 22 ianuarie 2019 17:09:46
Problema Trapez Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.73 kb

#include <cstdio>

#define dim 1 << 10

int N, M, K, ret;

int x[dim], y[dim], px[dim*dim], py[dim*dim];

int euclid( int, int );

void heapup( int );
void restore( int, int );
void swap( int, int );

int main()
{
    freopen("trapez.in", "r", stdin);
    freopen("trapez.out", "w", stdout);

    scanf("%d", &N);

    int i, j, a, b, c;

    for(i=1; i<=N; ++i)
             scanf("%d %d", x+i, y+i);

    for(i=1; i<=N; ++i)
             for(j=i+1; j<=N; ++j)
             {
                        ++ M;
                        px[M] = x[j] - x[i];
                        py[M] = y[j] - y[i];

                        c = euclid( px[M], py[M] );

                        while( c != 1 )
                        {
                               px[M] /= c;
                               py[M] /= c;
                               c = euclid( px[M], py[M] );
                        }
             }

    for(i=2; i<=M; ++i)
             heapup(i);

    for(i=M; i>1;)
    {
             swap(1, i);
             -- i;
             restore(1, i);
    }

    a = px[1]; b = py[1]; K = 1;

    for(i=2; i<=M; ++i)
             if( px[i] == a && py[i] == b )
             {
                 ++ K;
                 K -= K >= 666013 ? 666013 : 0;
             }
             else
             {
                 ret += (K * (K-1)) >> 1;
                 ret -= ret >= 666013 ? 666013 : 0;
                 K = 1;

                 a = px[i];
                 b = py[i];
             }

    printf("%d", ret);

    fclose(stdin); fclose(stdout);
    return 0;
}

int euclid( int x, int y )
{
     int r;
     while( y )
     {
            r = x % y;
            x = y;
            y = r;
     }

     return x;
}

void heapup( int k )
{
     if( k <= 1 )
         return;

     int t = k >> 1;

     if( px[t] < px[k] || px[t] == px[k] && py[t] < py[k] )
     {
         swap(t, k);
         heapup(t);
     }
}

void swap( int i, int j )
{
     px[i] ^= px[j] ^= px[i] ^= px[j];
     py[i] ^= py[j] ^= py[i] ^= py[j];
}

void restore( int r, int b )
{
     if( r << 1 <= b )
     {
         int stx, drx, sty, dry, x;

         stx = px[r << 1];
         sty = py[r << 1];

         if( (r << 1)+1 <= b )
         {
             drx = px[(r << 1)+1];
             dry = py[(r << 1)+1];
         }
         else
         {
             drx = stx-1;
             dry = sty-1;
         }

         if( stx > drx || stx == drx && sty > dry )
             x = r << 1;
         else
             x = (r << 1)+1;

         if( px[r] < px[x] || px[r] == px[x] && py[r] < py[x] )
         {
             swap(r, x);
             restore(x, b);
         }
     }
}