Cod sursa(job #2572280)

Utilizator dragossofiaSofia Dragos dragossofia Data 5 martie 2020 12:23:17
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>
#define Nmax 120003

using namespace std;

ifstream fin ("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct pct
{
 double x , y ;
}a[ Nmax ] , sol [ Nmax ];
int n , ct ;

void citire( )
{
  fin >> n ;
  for( int i = 1 ; i <= n ; i ++ )
        fin>>a[i].x>>a[i].y;
}

bool orientare( pct a , pct b , pct c )
{
 return (a.y - b.y)*(b.x - c.x) <= (b.y - c.y)*(a.x - c.x);
}

bool comp( pct a , pct b )
{
 return a.y < b. y || ( a.y == b.y && a.x < b.x ) ;
}

bool comp2( pct b , pct c )
{
 return orientare( a[1] , b , c ) ;
}

void do1 ( )
{
 int i , d1 , d2  ;
 d1 = 1 ;
 d2 = 2 ;
 for( i = 3 ; i <= n ; i ++)
    {
     if( orientare( a[ d1 ] , a [ d2 ] , a [ i ]) == true )
        {
         sol[ ++ ct ] = a[ d1 ] ;
         d1 = d2 ;
         d2 = i ;
        }
    else
        {
         d2 = i ;
        }
    }
 sol[ ++ ct ] = a[ d1 ] ;
 sol[ ++ ct ] = a[ d2 ] ;

 fout<<ct<<"\n";
 for( i = 1 ; i <= ct ; i ++ )
    fout<<fixed<<setprecision(6)<<sol[ i ].x<<" "<<sol[ i ].y<<"\n";
}

int main()
{
    citire();
    sort( a + 1 , a + n + 1 , comp );
    sort( a + 2 , a + n + 1 , comp2 );
    do1();
    return 0;
}