Pagini recente » Cod sursa (job #679341) | Cod sursa (job #2562265) | Cod sursa (job #2895908) | Cod sursa (job #2660311) | Cod sursa (job #2371410)
#include <bits/stdc++.h>
#define N 120005
#define inf 1000000005
using namespace std;
ifstream fin( "infasuratoare.in" );
ofstream fout( "infasuratoare.out" );
struct punct
{
double x, y;
};
int n;
punct A[N];
vector <punct> S;
void read()
{
int i;
fin >> n;
for ( i = 1; i <= n; ++i )
fin >> A[i].x >> A[i].y;
fin.close();
}
bool comp( punct X, punct Y )
{
return X.y < Y.y || X.y == Y.y && X.x < Y.x;
}
bool orientare1( punct X, punct Y )
{
return ( X.y - A[1].y ) * ( Y.x - X.x ) < ( Y.y - X.y ) * ( X.x - A[1].x );
}
bool orientare( punct X, punct Y, punct Z )
{
return ( Y.y - X.y ) * ( Z.x - Y.x ) < ( Z.y - Y.y ) * ( Y.x - X.x );
}
void solve()
{
int i;
sort( A + 1, A + n + 1, comp );
sort( A + 2, A + n + 1, orientare1 );
S.push_back( A[1] );
S.push_back( A[2] );
for ( i = 3; i <= n; ++i )
{
while ( !orientare( S[S.size()-2], S[S.size()-1], A[i] ) )
S.pop_back();
S.push_back( A[i] );
}
fout << S.size() << '\n';
/*int poz;
punct mini;
mini.x = mini.y = inf;
for ( i = 0; i < S.size(); ++i )
if ( S[i].y < mini.y || S[i].y == mini.y && S[i].x < mini.x )
{
mini = S[i];
poz = i;
}
for ( i = poz; i < S.size(); ++i )
fout << fixed << setprecision(6) << S[i].x << ' ' << S[i].y << '\n';
for ( i = 0; i < poz; ++i )
fout << fixed << setprecision(6) << S[i].x << ' ' << S[i].y << '\n';*/
for ( i = 0; i < S.size(); ++i )
fout << fixed << setprecision(6) << S[i].x << ' ' << S[i].y << '\n';
}
int main()
{
read();
solve();
fout.close();
return 0;
}