Pagini recente » Cod sursa (job #2406572) | Cod sursa (job #560941) | oji_2019_10 | Cod sursa (job #525851) | Cod sursa (job #2572280)
#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;
}