Pagini recente » Cod sursa (job #2804757) | Cod sursa (job #201773) | Cod sursa (job #2205552) | Cod sursa (job #658624) | Cod sursa (job #883392)
Cod sursa(job #883392)
#include <fstream>
#include <algorithm>
#include <iostream>
#include <iomanip>
using namespace std;
#define NMAX 120001
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
double x[NMAX], y[NMAX];
int ind[NMAX], s[NMAX];
int ip;
bool cmp( int i, int j )
{
return ( x[i] - x[ip] ) * ( y[j] - y[ip] ) < ( x[j] - x[ip] ) * ( y[i] - y[ip]);
}
bool ok( int x, int y, int k );
int main()
{
fin >> n;
fin >> x[0] >> y[0];
for( int i = 1; i < n; ++i )
{
fin >> x[i] >> y[i];
if( x[i] < x[ip] || ( x[i] == x[ip] && y[i] < y[ip] ) )
ip = i;
}
for( int i = 0; i < n; ++i )
ind[i] = i;
ind[ip] = ind[n-1];
sort( ind, ind+n-1, cmp );
int poz = 2;
s[0] = ip;
s[1] = ind[0];
for( int i = 1; i < n - 1; ++i )
{
while( poz >= 2 && ( !ok(s[poz - 2], s[poz - 1], ind[i] ) ) )
poz--;
s[poz++] = ind[i];
}
fout << poz << '\n';
for( int i = poz - 1; i >= 0; --i )
fout << x[s[i]] << ' ' << y[s[i]] << '\n';
fin.close();
fout.close();
return 0;
}
bool ok( int i, int j, int k )
{
return x[i] * y[k] + x[j] * y[i] + x[k] * y[j] > x[i] * y[j] + x[j] * y[k] + x[k] * y[i];
}