Pagini recente » Cod sursa (job #1019140) | Cod sursa (job #357376) | Cod sursa (job #1378144) | Cod sursa (job #1702824) | Cod sursa (job #2572435)
#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;
}