Pagini recente » Monitorul de evaluare | Cod sursa (job #1321946) | Rating Pudak Nurberdiyev (CristianBarbieru) | Cod sursa (job #1547331)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_N 120000
#define EPS 1e-10
typedef struct {
double x, y;
} Point;
typedef struct {
int s[MAX_N];
int ss;
} stack;
Point v[MAX_N];
stack L, U;
void myqsort( int begin, int end ) {
int b = begin, e = end;
Point pivot = v[rand() % (end - begin + 1) + begin], tmp;
while ( b <= e ) {
while ( v[b].x < pivot.x || (v[b].x == pivot.x && v[b].y < pivot.y) ) b++;
while ( v[e].x > pivot.x || (v[e].x == pivot.x && v[e].y > pivot.y) ) e--;
if ( b <= e ) {
tmp = v[b]; v[b] = v[e]; v[e] = tmp;
b++; e--;
}
}
if ( begin < e ) myqsort( begin, e );
if ( b < end ) myqsort( b, end );
}
// A.x A.y 1
// B.x B.y 1
// C.x C.y 1
__inline__ double ccw( Point *A, Point *B, Point *C ) {
return ( C->x - A->x ) * ( B->y - A->y ) - ( C->y - A->y ) * ( B->x - A->x );
}
int main(void) {
FILE *fin, *fout;
int N, i;
fin = fopen( "infasuratoare.in", "r" );
fscanf( fin, "%d", &N );
for ( i = 0; i < N; i++ ) {
fscanf( fin, "%lf%lf", &v[i].x, &v[i].y );
}
fclose( fin );
myqsort( 0, N - 1 );
for ( i = 0; i < N; i++ ) {
while ( L.ss > 1 && ccw( &v[L.s[L.ss-2]], &v[L.s[L.ss-1]], &v[i] ) >= 0 ) {
L.ss--;
}
L.s[L.ss++] = i;
}
for ( i = N - 1; i >= 0; i-- ) {
while ( U.ss > 1 && ccw( &v[U.s[U.ss-2]], &v[U.s[U.ss-1]], &v[i] ) >= 0 ) {
U.ss--;
}
U.s[U.ss++] = i;
}
fout = fopen( "infasuratoare.out", "w" );
L.ss--; U.ss--;
fprintf( fout, "%d\n", L.ss + U.ss );
for ( i = 0; i < L.ss; i++ ) {
fprintf( fout, "%.10f %.10f\n", v[L.s[i]].x, v[L.s[i]].y );
}
for ( i = 0; i < U.ss; i++ ) {
fprintf( fout, "%.10f %.10f\n", v[U.s[i]].x, v[U.s[i]].y );
}
fclose( fout );
return 0;
}