Pagini recente » Atasamentele paginii Profil vlad.bandac | Cod sursa (job #1139062) | Cod sursa (job #1063906) | Cod sursa (job #2923621)
// This program was written
// by Mircea Rebengiuc
// for problem https://infoarena.ro/problema/infasuratoare
// on 16.09.2022
#include <stdio.h>
#include <ctype.h>
#include <complex>
#define magic_sauce inline __attribute__((always_inline))
using ftype = double;
using cmplx = std::complex<ftype>;
FILE *fin, *fout;
magic_sauce cmplx fgetpoint(){
ftype x, y;
fscanf( fin, "%lf%lf", &x, &y );
return cmplx{ x, y };
}
magic_sauce void fputpoint( cmplx c ){
fprintf( fout, "%lf %lf\n", c.real(), c.imag() );
}
const int MAXN = 1.2e5;
const ftype MAXC = 1e9;
cmplx points[1 + MAXN];
ftype theta[MAXN];
cmplx stack[MAXN];
int sp;
void qsort( int begin, int end ){
int b = begin - 1, e = end + 1;
ftype p = theta[(begin + end) >> 1], aux;
cmplx auxc;
while( theta[++b] < p );
while( theta[--e] > p );
while( b < e ){
aux = theta[b];
theta[b] = theta[e];
theta[e] = aux;
auxc = points[b];
points[b] = points[e];
points[e] = auxc;
while( theta[++b] < p );
while( theta[--e] > p );
}
if( begin < e )
qsort( begin, e );
if( e + 1 < end )
qsort( e + 1, end );
}
// determinant
magic_sauce int orientation( cmplx a, cmplx b, cmplx c ){
ftype det = (b.imag() - a.imag()) * (c.real() - b.real()) - (b.real() - a.real()) * (c.imag() - b.imag());
if( det == 0 )
return 0;
return det < 0 ? 1 : 2;
}
magic_sauce bool intersects( cmplx a, cmplx b, cmplx c, cmplx d ){
// long live g4g
return (orientation( a, b, c ) != orientation( a, b, d )) && (orientation( c, d, a ) != orientation( c, d, b ));
}
int main(){
fin = fopen( "infasuratoare.in", "r" );
fout = fopen( "infasuratoare.out", "w" );
int n, i;
cmplx og = { 0, MAXC + 1 };
fscanf( fin, "%d", &n );
for( i = 0 ; i < n ; i++ ){
points[i] = fgetpoint();
if( points[i].imag() < og.imag() )
og = points[i];
}
for( i = 0 ; i < n ; i++ ){
points[i] -= og;
theta[i] = std::arg( points[i] ); // phase angle
}
qsort( 0, n - 1 );
points[n] = cmplx{ 0, 0 };
sp = 0;
for( i = 0 ; i <= n ; i++ ){
if( std::norm( points[i] ) > 0 || i >= n ){
while( sp >= 2 && !intersects( points[i], stack[sp - 2], { 0, 0 }, stack[sp - 1] ) )
sp--;
stack[sp++] = points[i];
}
}
fprintf( fout, "%d\n", sp );
fputpoint( og );
for( i = 0 ; i < sp - 1 ; i++ )
fputpoint( og + stack[i] );
fclose( fin );
fclose( fout );
return 0;
}