Cod sursa(job #2923621)

Utilizator mircea_007Mircea Rebengiuc mircea_007 Data 16 septembrie 2022 20:31:00
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.38 kb
// 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;
}