Pagini recente » Cod sursa (job #2796991) | Cod sursa (job #408886) | Cod sursa (job #1419643) | Monitorul de evaluare | Cod sursa (job #2190831)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define maxn 120000
using namespace std;
typedef struct
{
double px;
double py;
}poz;
poz v[maxn+5];
int inf[maxn+5];
double ccw ( poz a, poz b, poz c )
{ /// ( x2 - x1 ) * ( y3 - y1 ) - ( y2 - y1 ) * ( x3 - x1 ) < 0 => c este in stanga ab
double ans1 = ( b.px - a.px ) * ( c.py - a.py ), ans2 = ( b.py - a.py ) * ( c.px - a.px );
return ans1 - ans2;
}
bool cmp ( poz a, poz b )
{
return ccw ( v[0], a, b ) < 0;
}
int main ()
{
ifstream fin ( "infasuratoare.in" );
ofstream fout ( "infasuratoare.out" );
int n;
fin >> n;
int i;
for ( i = 0; i < n; i++ )
fin >> v[i].px >> v[i].py;
int np = 0;
for ( i = 1; i < n; i++ )
if ( v[0].px > v[i].px || ( v[0].px == v[i].px && v[0].py > v[i].py ) )
swap ( v[0], v[i] );
sort ( v + 1, v + n, cmp );
int nv = 2; /// nr varfuri pe infasuratoare
inf[0] = 0;
inf[1] = 1;
for ( i = 2; i < n; i++ )
{
while ( nv >= 2 && ccw ( v[inf[nv-2]], v[inf[nv-1]], v[i] ) >= 0 )
nv--;
inf[nv++] = i;
}
fout << nv << '\n';
for ( i = nv - 1; i >= 0; i-- )
fout << setprecision ( 9 ) << v[inf[i]].px << ' ' << v[inf[i]].py << '\n';
fin.close ();
fout.close ();
return 0;
}