Pagini recente » Cod sursa (job #510434) | Cod sursa (job #2958677) | Cod sursa (job #870502) | Cod sursa (job #2696637) | Cod sursa (job #3248877)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int stiva[120001];
int x1, y1, x2, y2;
struct cel
{
double x, y;
}v[120001];
int cmp ( cel a, cel b )
{
if ( a.x == b.x )
return a.y < b.y;
return a.x < b.x;
}
int arie( int xa, int ya, int xb, int yb, int xc, int yc )
{
return xa*yb + xb*yc + xc*ya - xc*yb - xa*yc - xb*ya;
}
int main()
{
int n, i;
f >> n;
for ( i = 1; i <= n; i ++ )
f >> v[i].x >> v[i].y;
sort ( v + 1, v + n + 1, cmp );
x1 = v[1].x;
y1 = v[1].y;
x2 = v[n].x;
y2 = v[n].y;
int k = 1;
stiva[k] = 1;
for ( i = 2; i <= n; i ++ )
{
if ( arie ( x1, y1, x2, y2, v[i].x, v[i].y ) < 0 )
{
while ( k > 1 && arie ( v[stiva[k-1]].x, v[stiva[k-1]].y, v[stiva[k]].x, v[stiva[k]].y, v[i].x, v[i].y ) < 0)
k --;
k ++;
stiva[k] = i;
}
}
k ++;
int ck = k;
stiva[k] = n;
for ( i = n - 1; i >= 1; i -- )
{
if ( arie ( x1, y1, x2, y2, v[i].x, v[i].y ) > 0 )
{
while ( k > ck && arie ( v[stiva[k-1]].x, v[stiva[k-1]].y, v[stiva[k]].x, v[stiva[k]].y, v[i].x, v[i].y ) < 0)
k --;
k ++;
stiva[k] = i;
}
}
g << k << '\n';
for ( i = 2; i <= k; i ++ )
g << fixed << setprecision(6) << v[stiva[i]].x << " " << v[stiva[i]].y << '\n';
g << fixed << setprecision(6) << v[1].x << " " << v[1].y;
return 0;
}