24th - 2nd Round Solutions

Γενικά θέματα για το διαγωνισμό. Ερωτήσεις, προτάσεις και ό,τι άλλο ταιριάζει.
Απάντηση
Άβαταρ μέλους
mariosal
Δημοσιεύσεις: 63
Εγγραφή: Σάβ Μαρ 20, 2010 12:00 am
Τοποθεσία: Χολαργός, Ελλάδα
Επικοινωνία:

24th - 2nd Round Solutions

Δημοσίευση από mariosal » Τετ Μαρ 07, 2012 2:56 pm

pulsars: https://github.com/mariosal/algo/blob/m ... /pulsars.c

Κώδικας: Επιλογή όλων

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    unsigned short x, y;
    int id;
} point;

point min;

int cross( point a, point b, point c ) {
    return ( int )( b.x - a.x ) * ( c.y - a.y ) - ( b.y - a.y ) * ( c.x - a.x );
}
unsigned distance2( point a, point b ) {
    return ( unsigned )( a.x - b.x ) * ( a.x - b.x ) + ( a.y - b.y ) * ( a.y - b.y );
}

int pCompare( const void *a, const void *b ) {
    int wise;
    unsigned d, d2;

    wise = cross( min, *( point* )a, *( point* )b );
    if ( wise > 0 ) {
        return -1;
    }
    if ( wise < 0 ) {
        return 1;
    }

    d = distance2( min, *( point* )a );
    d2 = distance2( min, *( point* )b );
    if ( d < d2 ) {
        return -1;
    }
    return 1;
}
int hCompare( const void *a, const void *b ) {
    return ( ( point* )a )->id - ( ( point* )b )->id;
}

int main() {
    int n, m, i;
    point *p, *hull;

    freopen( "pulsars.in", "r", stdin );
    freopen( "pulsars.out", "w", stdout );

    scanf( "%d", &n );
    p = ( point* )malloc( n * sizeof( point ) );
    hull = ( point* )malloc( n * sizeof( point ) );

    for ( i = 0; i < n; i += 1 ) {
        scanf( "%hu %hu", &p[ i ].x, &p[ i ].y );
        p[ i ].id = i + 1;

        if ( !i || min.y > p[ i ].y || ( min.y == p[ i ].y && min.x > p[ i ].x ) ) {
            min = p[ i ];
        }
    }

    qsort( p, n, sizeof( point ), pCompare );
    m = 0;
    for ( i = 0; i < n; i += 1 ) {
        while ( m >= 2 && cross( hull[ m - 2 ], hull[ m - 1 ], p[ i ] ) <= 0 ) {
            m -= 1;
        }

        hull[ m ] = p[ i ];
        m += 1;
    }

    qsort( hull, m, sizeof( point ), hCompare );
    printf( "%d\n", m );
    for ( i = 0; i < m; i += 1 ) {
        printf( "%d\n", hull[ i ].id );
    }

    return 0;
}
operators: https://github.com/mariosal/algo/blob/m ... perators.c

Κώδικας: Επιλογή όλων

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main() {
    int n, i, j, min[ 2 ], *a;

    freopen( "operators.in", "r", stdin );
    freopen( "operators.out", "w", stdout );

    scanf( "%d", &n );
    a = ( int* )malloc( n * sizeof( int ) );

    for ( i = 0; i < n; i += 1 ) {
        scanf( "%d", &a[ i ] );
    }

    i = 0;
    j = n - 1;
    min[ 0 ] = a[ i ];
    min[ 1 ] = a[ j ];
    while ( i < j ) {
        if ( abs( min[ 0 ] + min[ 1 ] ) > abs( a[ i ] + a[ j ] ) ) {
            min[ 0 ] = a[ i ];
            min[ 1 ] = a[ j ];
            if ( a[ i ] + a[ j ] == 0 ) {
                break;
            }
        }
        if ( a[ i ] + a[ j ] > 0 ) {
            j -= 1;
        }
        else {
            i += 1;
        }
    }

    printf( "%d %d\n", min[ 0 ], min[ 1 ] );

    return 0;
}

infinity
Δημοσιεύσεις: 38
Εγγραφή: Σάβ Νοέμ 26, 2011 4:08 pm

Re: 24th - 2nd Round Solutions

Δημοσίευση από infinity » Τετ Μαρ 07, 2012 3:28 pm

operators:
[pastebin]http://pastebin.com/4EYpJ3uW[/pastebin]

Άβαταρ μέλους
kernelpanic
Δημοσιεύσεις: 404
Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
Τοποθεσία: Αθήνα

Re: 24th - 2nd Round Solutions

Δημοσίευση από kernelpanic » Τετ Μαρ 07, 2012 4:49 pm

Spoiler: show
[pastebin]http://pastebin.com/Sw6HViAZ[/pastebin]
Οι πιθανές τιμές των χ,y είναι 40001.
Από τα σημεία που βρίσκονται σε μια οποιαδήποτε ευθεία, μόνο τα 2 ακραία είναι δυνατό να ανήκουν στο πολύγωνο-τα εσωτερικά περικλείονται.
Επομένως, το πολύ 80.000 σημεία ανήκουν στο πολύγωνο.
Από'κει και πέρα ένας αλγόριθμος Ο(Ν2) πιάνει αρκετές μονάδες ;)

Εδώ, ο Ο(Ν) αλγόριθμος με τη βοήθεια μιας στοίβας και του εξωτερικού γινομένου βρίσκει μια γραμμή που αρχίζει στο ελάχιστο χ, τελειώνει εκεί που είναι μέγιστο, και στρέφει tequila προς τα πάνω, και μια γραμμή που αρχίζει στο ελάχιστο χ, τελειώνει εκεί που είναι μέγιστο, και στρέφει tequila προς τα κάτω, ενώ τα πιθανά σημεία περιέχονται στο πολύγωνο που αυτές οι δύο σχηματίζουν.
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.

themis5
Δημοσιεύσεις: 5
Εγγραφή: Δευ Ιαν 24, 2011 6:43 pm
Επικοινωνία:

Re: 24th - 2nd Round Solutions

Δημοσίευση από themis5 » Τετ Μαρ 07, 2012 5:53 pm

Έχει και κάποιες ιδιότητες για το BSHEEP του spoj.

Κώδικας: Επιλογή όλων

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <algorithm>

using namespace std;

struct Point {
    long long int x;
    long long int y;
    int key;
    double distance;
};

Point *Q;
int mink;

long long int CCW( Point A, Point B, Point C ) {
    return ( B.x - A.x ) * ( C.y - A.y ) - ( B.y - A.y ) * ( C.x - A.x );
}

void Swap( Point *A, int i, int j ) {
    Point temp;
    temp = A[ i ];
    A[ i ] = A[ j ];
    A[ j ] = temp;
}

int cmp( const void * a, const void * b ) {
    Point A = *( Point* )a;
    Point B = *( Point* )b;
    if ( CCW( Q[ 0 ], A, B ) > 0 ) {
        return -1;
    }
    if ( CCW( Q[ 0 ], A, B ) == 0 ) {
        return A.distance - B.distance;
    }
    return 1;
}

bool samePoint( Point A, Point B ) {
    if ( A.x == B.x && A.y == B.y ) {
        return true;
    }
    return false;
}

FILE *in = fopen( "pulsars.in", "r" ), *out = fopen( "pulsars.out", "w" );
int N, i, *S, j, ccw;
priority_queue< int > seq;

int main() {
    fscanf( in, "%d", &N );

    Q = ( Point* )malloc( N * sizeof( Point ) );
    S = ( int* )malloc( N * sizeof( int ) );

    mink = 0;
    for ( i = 0; i < N; ++i ) {
        fscanf( in, "%lld %lld", &Q[ i ].x, &Q[ i ].y );
        Q[ i ].key = i;
        if ( Q[ i ].y < Q[ mink ].y ) {
            mink = i;
        }
        if ( Q[ i ].y == Q[ mink ].y ) {
            if ( Q[ i ].x < Q[ mink ].x ) {
                mink = i;
            }
        }
    }

    for ( i = 0; i < N; ++i ) {
        if ( mink != i ) {
            Q[ i ].distance = sqrt( 
                pow( (double)( Q[ i ].x - Q[ mink ].x ), 2 ) +
                pow( (double)( Q[ i ].y - Q[ mink ].y ), 2 )
            );
        }
    }
    Q[ mink ].distance = -1;
    Swap( Q, mink, 0 );
    qsort( Q + 1, N - 1, sizeof( Point ), cmp );

    S[ 0 ] = 0;
    j = 1;
    i = 1;
    // Graham
    while ( i < N ) {
        if ( j < 2 ) {
            if ( !samePoint( Q[ S[ j - 1 ] ], Q[ i ] ) ) {
                S[ j ] = i;
                ++j;
            }
            ++i;
            continue;
        }
        ccw = CCW( Q[ S[ j - 2 ] ], Q[ S[ j - 1 ] ], Q[ i ] );
        if ( ccw > 0 ) {
            S[ j ] = i;
            ++j;
            ++i;
        }
        else {
            if ( !samePoint( Q[ S[ j - 1 ] ], Q[ i ] ) ) {
                --j;
            }
            else {
                if ( Q[ S[ j - 1 ] ].key > Q[ i ].key ) {
                    S[ j - 1 ] = i;
                }
                ++i;
            }
        }
    }

    //Output
    for ( i = 0; i < j; ++i ) {
        seq.push( -( Q[ S[ i ] ].key + 1 ) );
    }
    fprintf( out, "%i\n", (int)seq.size() );
    while ( !seq.empty() ) {
        fprintf( out, "%i\n", -seq.top() );
        seq.pop();
    }

    free( Q );
    free( S );
    
    return 0;
}

infinity
Δημοσιεύσεις: 38
Εγγραφή: Σάβ Νοέμ 26, 2011 4:08 pm

Re: 24th - 2nd Round Solutions

Δημοσίευση από infinity » Παρ Μαρ 09, 2012 9:33 pm

themis5 έγραψε:Έχει και κάποιες ιδιότητες για το BSHEEP του spoj.

Κώδικας: Επιλογή όλων

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <algorithm>

using namespace std;

struct Point {
    long long int x;
    long long int y;
    int key;
    double distance;
};

Point *Q;
int mink;

long long int CCW( Point A, Point B, Point C ) {
    return ( B.x - A.x ) * ( C.y - A.y ) - ( B.y - A.y ) * ( C.x - A.x );
}

void Swap( Point *A, int i, int j ) {
    Point temp;
    temp = A[ i ];
    A[ i ] = A[ j ];
    A[ j ] = temp;
}

int cmp( const void * a, const void * b ) {
    Point A = *( Point* )a;
    Point B = *( Point* )b;
    if ( CCW( Q[ 0 ], A, B ) > 0 ) {
        return -1;
    }
    if ( CCW( Q[ 0 ], A, B ) == 0 ) {
        return A.distance - B.distance;
    }
    return 1;
}

bool samePoint( Point A, Point B ) {
    if ( A.x == B.x && A.y == B.y ) {
        return true;
    }
    return false;
}

FILE *in = fopen( "pulsars.in", "r" ), *out = fopen( "pulsars.out", "w" );
int N, i, *S, j, ccw;
priority_queue< int > seq;

int main() {
    fscanf( in, "%d", &N );

    Q = ( Point* )malloc( N * sizeof( Point ) );
    S = ( int* )malloc( N * sizeof( int ) );

    mink = 0;
    for ( i = 0; i < N; ++i ) {
        fscanf( in, "%lld %lld", &Q[ i ].x, &Q[ i ].y );
        Q[ i ].key = i;
        if ( Q[ i ].y < Q[ mink ].y ) {
            mink = i;
        }
        if ( Q[ i ].y == Q[ mink ].y ) {
            if ( Q[ i ].x < Q[ mink ].x ) {
                mink = i;
            }
        }
    }

    for ( i = 0; i < N; ++i ) {
        if ( mink != i ) {
            Q[ i ].distance = sqrt( 
                pow( (double)( Q[ i ].x - Q[ mink ].x ), 2 ) +
                pow( (double)( Q[ i ].y - Q[ mink ].y ), 2 )
            );
        }
    }
    Q[ mink ].distance = -1;
    Swap( Q, mink, 0 );
    qsort( Q + 1, N - 1, sizeof( Point ), cmp );

    S[ 0 ] = 0;
    j = 1;
    i = 1;
    // Graham
    while ( i < N ) {
        if ( j < 2 ) {
            if ( !samePoint( Q[ S[ j - 1 ] ], Q[ i ] ) ) {
                S[ j ] = i;
                ++j;
            }
            ++i;
            continue;
        }
        ccw = CCW( Q[ S[ j - 2 ] ], Q[ S[ j - 1 ] ], Q[ i ] );
        if ( ccw > 0 ) {
            S[ j ] = i;
            ++j;
            ++i;
        }
        else {
            if ( !samePoint( Q[ S[ j - 1 ] ], Q[ i ] ) ) {
                --j;
            }
            else {
                if ( Q[ S[ j - 1 ] ].key > Q[ i ].key ) {
                    S[ j - 1 ] = i;
                }
                ++i;
            }
        }
    }

    //Output
    for ( i = 0; i < j; ++i ) {
        seq.push( -( Q[ S[ i ] ].key + 1 ) );
    }
    fprintf( out, "%i\n", (int)seq.size() );
    while ( !seq.empty() ) {
        fprintf( out, "%i\n", -seq.top() );
        seq.pop();
    }

    free( Q );
    free( S );
    
    return 0;
}
φίλε θέμη για Ν=1000000 τα φτύνει λίγο

infinity@netbook-debian:~/Desktop$ time ./pulsars

real 0m6.961s
user 0m6.848s
sys 0m0.088s

μπορεί στους υπολογιστές της hellenico να είναι λιγότερο, αλλά εδώ το έχασες λίγο :P

karantias
Δημοσιεύσεις: 4
Εγγραφή: Τρί Σεπ 06, 2011 6:16 pm

Re: 24th - 2nd Round Solutions

Δημοσίευση από karantias » Σάβ Μαρ 10, 2012 2:29 am

Να πω την αλήθεια έχω χάσει τη λύση που είχα υποβάλλει, ελπίζω να μπορέσω να την δω κάποια στιγμή από το hellenico.

Αυτή η λύση είναι παρόμοια, modification της λύσης μου για το bsheep.

Κώδικας: Επιλογή όλων

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int x, y;
    unsigned int id;
} point;

point M;

long long ccw( point A, point B, point C ) {
    return ( B.x - A.x ) * ( C.y - A.y ) - ( B.y - A.y ) * ( C.x - A.x );
}

unsigned int dist( point A, point B ) {
    return ( B.x - A.x ) * ( B.x - A.x ) + ( B.y - A.y ) * ( B.y - A.y );
}

int cmpolar( const void *a, const void *b ) {
    point aa = *( point* )a;
    point bb = *( point* )b;
    unsigned int dist1, dist2; //else overflow for N=10^6
    long long angle = ccw( M, aa, bb );
    if ( angle > 0 ) {
        return -1;
    }
    if ( angle < 0 ) {
        return 1;
    }

    //angle == 0: points collinear
    dist1 = dist( M, aa );
    dist2 = dist( M, bb );
    if ( dist1 < dist2 ) {
        return -1;
    }
    if ( dist1 > dist2 ) {
        return 1;
    }

    //resort to id comparison
    return cmpid( a, b );
}
int cmpid( const void *a, const void *b ) {
    return ( ( point* )a )->id - ( ( point* )b )->id;
}

int main( void ) {
    FILE *fin = fopen( "pulsars.txt", "r" );
    FILE *fout = fopen( "pulsars.out", "w" );
    unsigned int N, i, hn = 0;
    point *Q, *H;

    //N points
    fscanf( fin, "%u", &N );
    Q = ( point* )malloc( N * sizeof( point ) );
    H = ( point* )malloc( N * sizeof( point ) );


    //scan each point
    for ( i = 0; i < N; ++i ) {
        fscanf( fin, "%d %d", &Q[ i ].x, &Q[ i ].y );
        Q[ i ].id = i + 1;
    }

    //find minimum
    M = Q[ 0 ];
    for ( i = 1; i < N; ++i ) {
        if ( Q[ i ].y < M.y || ( Q[ i ].y == M.y && Q[ i ].x < M.x ) ) {
            M = Q[ i ];
        }
    }

    //sort by polar angle
    qsort( Q, N, sizeof( point ), cmpolar );

    //create the convex hull
    //points >= 10 so we put in the first 3 anyway
    i = 0;
    H[ hn++ ] = Q[ i++ ];
    H[ hn++ ] = Q[ i++ ];
    H[ hn++ ] = Q[ i++ ];
    for ( i = i; i < N; ++i ) {
        if ( i && Q[ i - 1 ].x == Q[ i ].x && Q[ i - 1 ].y == Q[ i ].y ) {
            continue;
        }
        while ( hn >= 2 && ccw( H[ hn - 2 ], H[ hn - 1 ], Q[ i ] ) <= 0 ) {
            --hn;
        }
        H[ hn++ ] = Q[ i ];
    }

    //sort by id
    qsort( H, hn, sizeof( point ), cmpid );

    //print out the hull points
    fprintf( fout, "%d\n", hn );
    for ( i = 0; i < hn; ++i ) {
        fprintf( fout, "%u\n", H[ i ].id );
    }

    free( Q );
    free( H );

    return 0;
}

themis5
Δημοσιεύσεις: 5
Εγγραφή: Δευ Ιαν 24, 2011 6:43 pm
Επικοινωνία:

Re: 24th - 2nd Round Solutions

Δημοσίευση από themis5 » Σάβ Μαρ 10, 2012 2:41 am

infinity έγραψε:
themis5 έγραψε:Έχει και κάποιες ιδιότητες για το BSHEEP του spoj.

Κώδικας: Επιλογή όλων

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <algorithm>

using namespace std;

struct Point {
    long long int x;
    long long int y;
    int key;
    double distance;
};

Point *Q;
int mink;

long long int CCW( Point A, Point B, Point C ) {
    return ( B.x - A.x ) * ( C.y - A.y ) - ( B.y - A.y ) * ( C.x - A.x );
}

void Swap( Point *A, int i, int j ) {
    Point temp;
    temp = A[ i ];
    A[ i ] = A[ j ];
    A[ j ] = temp;
}

int cmp( const void * a, const void * b ) {
    Point A = *( Point* )a;
    Point B = *( Point* )b;
    if ( CCW( Q[ 0 ], A, B ) > 0 ) {
        return -1;
    }
    if ( CCW( Q[ 0 ], A, B ) == 0 ) {
        return A.distance - B.distance;
    }
    return 1;
}

bool samePoint( Point A, Point B ) {
    if ( A.x == B.x && A.y == B.y ) {
        return true;
    }
    return false;
}

FILE *in = fopen( "pulsars.in", "r" ), *out = fopen( "pulsars.out", "w" );
int N, i, *S, j, ccw;
priority_queue< int > seq;

int main() {
    fscanf( in, "%d", &N );

    Q = ( Point* )malloc( N * sizeof( Point ) );
    S = ( int* )malloc( N * sizeof( int ) );

    mink = 0;
    for ( i = 0; i < N; ++i ) {
        fscanf( in, "%lld %lld", &Q[ i ].x, &Q[ i ].y );
        Q[ i ].key = i;
        if ( Q[ i ].y < Q[ mink ].y ) {
            mink = i;
        }
        if ( Q[ i ].y == Q[ mink ].y ) {
            if ( Q[ i ].x < Q[ mink ].x ) {
                mink = i;
            }
        }
    }

    for ( i = 0; i < N; ++i ) {
        if ( mink != i ) {
            Q[ i ].distance = sqrt( 
                pow( (double)( Q[ i ].x - Q[ mink ].x ), 2 ) +
                pow( (double)( Q[ i ].y - Q[ mink ].y ), 2 )
            );
        }
    }
    Q[ mink ].distance = -1;
    Swap( Q, mink, 0 );
    qsort( Q + 1, N - 1, sizeof( Point ), cmp );

    S[ 0 ] = 0;
    j = 1;
    i = 1;
    // Graham
    while ( i < N ) {
        if ( j < 2 ) {
            if ( !samePoint( Q[ S[ j - 1 ] ], Q[ i ] ) ) {
                S[ j ] = i;
                ++j;
            }
            ++i;
            continue;
        }
        ccw = CCW( Q[ S[ j - 2 ] ], Q[ S[ j - 1 ] ], Q[ i ] );
        if ( ccw > 0 ) {
            S[ j ] = i;
            ++j;
            ++i;
        }
        else {
            if ( !samePoint( Q[ S[ j - 1 ] ], Q[ i ] ) ) {
                --j;
            }
            else {
                if ( Q[ S[ j - 1 ] ].key > Q[ i ].key ) {
                    S[ j - 1 ] = i;
                }
                ++i;
            }
        }
    }

    //Output
    for ( i = 0; i < j; ++i ) {
        seq.push( -( Q[ S[ i ] ].key + 1 ) );
    }
    fprintf( out, "%i\n", (int)seq.size() );
    while ( !seq.empty() ) {
        fprintf( out, "%i\n", -seq.top() );
        seq.pop();
    }

    free( Q );
    free( S );
    
    return 0;
}
φίλε θέμη για Ν=1000000 τα φτύνει λίγο

infinity@netbook-debian:~/Desktop$ time ./pulsars

real 0m6.961s
user 0m6.848s
sys 0m0.088s

μπορεί στους υπολογιστές της hellenico να είναι λιγότερο, αλλά εδώ το έχασες λίγο :P
Για το testcase του Σωτήρη το οποίο έχει το ίδιο μέγεθος:
Berners:pulsars themicp$ time ./pulsars

real 0m0.525s
user 0m0.507s
sys 0m0.016s

Εσύ σε ποιο το τρέχεις;

infinity
Δημοσιεύσεις: 38
Εγγραφή: Σάβ Νοέμ 26, 2011 4:08 pm

Re: 24th - 2nd Round Solutions

Δημοσίευση από infinity » Σάβ Μαρ 10, 2012 3:42 pm

themis5 έγραψε:
infinity έγραψε:
themis5 έγραψε:Έχει και κάποιες ιδιότητες για το BSHEEP του spoj.

Κώδικας: Επιλογή όλων

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <algorithm>

using namespace std;

struct Point {
    long long int x;
    long long int y;
    int key;
    double distance;
};

Point *Q;
int mink;

long long int CCW( Point A, Point B, Point C ) {
    return ( B.x - A.x ) * ( C.y - A.y ) - ( B.y - A.y ) * ( C.x - A.x );
}

void Swap( Point *A, int i, int j ) {
    Point temp;
    temp = A[ i ];
    A[ i ] = A[ j ];
    A[ j ] = temp;
}

int cmp( const void * a, const void * b ) {
    Point A = *( Point* )a;
    Point B = *( Point* )b;
    if ( CCW( Q[ 0 ], A, B ) > 0 ) {
        return -1;
    }
    if ( CCW( Q[ 0 ], A, B ) == 0 ) {
        return A.distance - B.distance;
    }
    return 1;
}

bool samePoint( Point A, Point B ) {
    if ( A.x == B.x && A.y == B.y ) {
        return true;
    }
    return false;
}

FILE *in = fopen( "pulsars.in", "r" ), *out = fopen( "pulsars.out", "w" );
int N, i, *S, j, ccw;
priority_queue< int > seq;

int main() {
    fscanf( in, "%d", &N );

    Q = ( Point* )malloc( N * sizeof( Point ) );
    S = ( int* )malloc( N * sizeof( int ) );

    mink = 0;
    for ( i = 0; i < N; ++i ) {
        fscanf( in, "%lld %lld", &Q[ i ].x, &Q[ i ].y );
        Q[ i ].key = i;
        if ( Q[ i ].y < Q[ mink ].y ) {
            mink = i;
        }
        if ( Q[ i ].y == Q[ mink ].y ) {
            if ( Q[ i ].x < Q[ mink ].x ) {
                mink = i;
            }
        }
    }

    for ( i = 0; i < N; ++i ) {
        if ( mink != i ) {
            Q[ i ].distance = sqrt( 
                pow( (double)( Q[ i ].x - Q[ mink ].x ), 2 ) +
                pow( (double)( Q[ i ].y - Q[ mink ].y ), 2 )
            );
        }
    }
    Q[ mink ].distance = -1;
    Swap( Q, mink, 0 );
    qsort( Q + 1, N - 1, sizeof( Point ), cmp );

    S[ 0 ] = 0;
    j = 1;
    i = 1;
    // Graham
    while ( i < N ) {
        if ( j < 2 ) {
            if ( !samePoint( Q[ S[ j - 1 ] ], Q[ i ] ) ) {
                S[ j ] = i;
                ++j;
            }
            ++i;
            continue;
        }
        ccw = CCW( Q[ S[ j - 2 ] ], Q[ S[ j - 1 ] ], Q[ i ] );
        if ( ccw > 0 ) {
            S[ j ] = i;
            ++j;
            ++i;
        }
        else {
            if ( !samePoint( Q[ S[ j - 1 ] ], Q[ i ] ) ) {
                --j;
            }
            else {
                if ( Q[ S[ j - 1 ] ].key > Q[ i ].key ) {
                    S[ j - 1 ] = i;
                }
                ++i;
            }
        }
    }

    //Output
    for ( i = 0; i < j; ++i ) {
        seq.push( -( Q[ S[ i ] ].key + 1 ) );
    }
    fprintf( out, "%i\n", (int)seq.size() );
    while ( !seq.empty() ) {
        fprintf( out, "%i\n", -seq.top() );
        seq.pop();
    }

    free( Q );
    free( S );
    
    return 0;
}
φίλε θέμη για Ν=1000000 τα φτύνει λίγο

infinity@netbook-debian:~/Desktop$ time ./pulsars

real 0m6.961s
user 0m6.848s
sys 0m0.088s

μπορεί στους υπολογιστές της hellenico να είναι λιγότερο, αλλά εδώ το έχασες λίγο :P
Για το testcase του Σωτήρη το οποίο έχει το ίδιο μέγεθος:
Berners:pulsars themicp$ time ./pulsars

real 0m0.525s
user 0m0.507s
sys 0m0.016s

Εσύ σε ποιο το τρέχεις;
Στου σωτήρη, απλως το τρέχω απο netbook οπότε παίζει να φταίει και αυτο λίγο (ως πολύ) :P

feedWARd
Δημοσιεύσεις: 72
Εγγραφή: Κυρ Δεκ 21, 2008 3:32 pm

Re: 24th - 2nd Round Solutions

Δημοσίευση από feedWARd » Δευ Μαρ 12, 2012 3:35 pm

infinity έγραψε:operators:
[pastebin]http://pastebin.com/4EYpJ3uW[/pastebin]
Πολύ καλή λύση! Κάποιες μικρές παρατηρήσεις:
1. Αν θες να βάλεις έλεγχο στην scanf το καλύτερο που έχεις να κάνεις είναι να βλέπεις αν διάβασες τόσα ορίσματα όσα περίμενες, π.χ. scanf("%d %d", &a, &b) == 2. Στην συγκεκριμένη περίπτωση δεν έχει διαφορά, αλλά γενικά είναι καλή πρακτική.
2. Ποιος ο λόγος να χρησιμοποιήσεις fabs αντί για abs;
3. To σημαντικότερο: αφού το neg ουστιαστικά είναι μια στοίβα, είναι πολύ καλύτερο να χρησιμοποιήσεις την δομή stack της stl.Δες τι κάνει η push_back στο vector.

infinity
Δημοσιεύσεις: 38
Εγγραφή: Σάβ Νοέμ 26, 2011 4:08 pm

Re: 24th - 2nd Round Solutions

Δημοσίευση από infinity » Δευ Μαρ 12, 2012 6:57 pm

feedWARd έγραψε:
infinity έγραψε:operators:
[pastebin]http://pastebin.com/4EYpJ3uW[/pastebin]
Πολύ καλή λύση! Κάποιες μικρές παρατηρήσεις:
1. Αν θες να βάλεις έλεγχο στην scanf το καλύτερο που έχεις να κάνεις είναι να βλέπεις αν διάβασες τόσα ορίσματα όσα περίμενες, π.χ. scanf("%d %d", &a, &b) == 2. Στην συγκεκριμένη περίπτωση δεν έχει διαφορά, αλλά γενικά είναι καλή πρακτική.
2. Ποιος ο λόγος να χρησιμοποιήσεις fabs αντί για abs;
3. To σημαντικότερο: αφού το neg ουστιαστικά είναι μια στοίβα, είναι πολύ καλύτερο να χρησιμοποιήσεις την δομή stack της stl.Δες τι κάνει η push_back στο vector.
1. βασικά, δεν είναι τόσο για έλεγχο της scanf όσο το ότι προσπαθούσα να μειώσω όσο το δυνατόν περισσότερο τις γραμμές κώδικα (ναι έχω ένα κόλλημα με αυτό :P)
2. Κανένας ουσιαστικός λόγος, απλώς τη fabs χρησιμοποιούσα ανέκαθεν :P.
3. Ναι, απλώς επειδή δεν γνωρίζω και πολύ καλα την stl χρησιμοποίησα vector, για να κρατήσω τις αρνητικές τιμές, που είναι το data structure που ξέρω καλύτερα...

ευχαριστώ για τα καλά σου λόγια, αλλά και για τις συμβουλές...

feedWARd
Δημοσιεύσεις: 72
Εγγραφή: Κυρ Δεκ 21, 2008 3:32 pm

Re: 24th - 2nd Round Solutions

Δημοσίευση από feedWARd » Δευ Μαρ 12, 2012 8:29 pm

infinity έγραψε: 1. βασικά, δεν είναι τόσο για έλεγχο της scanf όσο το ότι προσπαθούσα να μειώσω όσο το δυνατόν περισσότερο τις γραμμές κώδικα (ναι έχω ένα κόλλημα με αυτό :P)
Τότε απλά scanf(...) && ....
infinity έγραψε: 3. Ναι, απλώς επειδή δεν γνωρίζω και πολύ καλα την stl χρησιμοποίησα vector, για να κρατήσω τις αρνητικές τιμές, που είναι το data structure που ξέρω καλύτερα...
Οκ, απλα πρόσεξε οτι η push_back είναι O(N) στο vector.

kostantinaras
Δημοσιεύσεις: 14
Εγγραφή: Πέμ Μαρ 08, 2012 3:40 pm

Re: 24th - 2nd Round Solutions

Δημοσίευση από kostantinaras » Δευ Μαρ 19, 2012 9:11 pm

Και η δικιά μου:
[pastebin]http://pastebin.com/qyYyYkrT[/pastebin]
Ξέρω οτι είναι ολίγον ο,τι νάνε! :?
In a world without walls and fenches who needs Windows and Gates?

Άβαταρ μέλους
mariosal
Δημοσιεύσεις: 63
Εγγραφή: Σάβ Μαρ 20, 2010 12:00 am
Τοποθεσία: Χολαργός, Ελλάδα
Επικοινωνία:

Re: 24th - 2nd Round Solutions

Δημοσίευση από mariosal » Τρί Μαρ 20, 2012 12:19 am

kostantinaras έγραψε:[pastebin]http://pastebin.com/qyYyYkrT[/pastebin]
Εικόνα

https://xkcd.com/292/

infinity
Δημοσιεύσεις: 38
Εγγραφή: Σάβ Νοέμ 26, 2011 4:08 pm

Re: 24th - 2nd Round Solutions

Δημοσίευση από infinity » Τρί Μαρ 20, 2012 4:19 pm

Ναι όντως γιατι τόσα goto @konstantinaras? :P

Απάντηση