Cod sursa(job #2572435)

Utilizator dragossofiaSofia Dragos dragossofia Data 5 martie 2020 12:48:31
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 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 , imini , xmini , ymini;

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 comp2( pct b , pct c )
{
 return orientare( a[1] , b , c ) ;
}

void do1 ( )
{
 int i , d1 , d2 , x , y  ;
 vector < int > S;
 S.push_back( 1 );
 S.push_back( 2 );
 for( i = 3 ; i <= n ; i ++)
    {
     while( orientare( a[ S [ S.size() - 2 ] ] , a [ S [ S.size() - 1 ] ] , a [ i ]) == false )
        {
         S.pop_back();
        }
    S.push_back( i ) ;
    }
 fout<<S.size()<<"\n";
 for( i = 0 ; i < S.size() ; i ++ )
    fout<<fixed<<setprecision(6)<<a[ S [ i ] ].x<<" "<<a[ S [ i ] ].y<<"\n";
}

int main()
{
    citire();
    imini = 1 ;
    xmini= a[ 1 ] . x;
    ymini= a[ 1 ] . y;
    for( int i = 2 ; i<= n ; i++ )
        if( a[ i ].x < xmini || ( a[ i ].x == xmini && a[ i ] . y < ymini )  )
            {
             xmini = a[ i ].x;
             ymini = a[ i ].y;
             imini = i ;
            }
    swap( a[ 1 ] , a[ imini ] );
    sort( a + 2 , a + n + 1 , comp2 );
    do1();
    return 0;
}