Pagini recente » Cod sursa (job #812504) | Cod sursa (job #1304813) | Cod sursa (job #2401959) | Cod sursa (job #930624) | Cod sursa (job #2869113)
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct puncte
{
double x, y;
}punct[120020],s[120020];
double product(puncte a , puncte b , puncte c)
{
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
bool cmp(puncte c , puncte b)
{
return product(punct[1] , c , b) < 0;
}
int n , vf , poz;
int main()
{
f >> n;
for ( int i = 1 ; i <= n ; i++)
{
f >> punct[i].x >> punct[i].y;
}
poz = 1;
for ( int i = 2 ; i <= n ; i++)
if( ( punct[i].x < punct[poz].x) || (punct[i].x == punct[poz].x && punct[i].y < punct[poz].y))
poz = i;
swap(punct[1] , punct[poz]);
sort(punct + 2 , punct + n + 1 , cmp);
s[1] = punct[1];
s[2] = punct[2];
vf = 2;
for ( int i = 3 ; i <= n ; i++)
{
while( vf >= 2 && product(s[vf-1] , s[vf] , punct[i]) > 0)
vf-- ;
vf++;
s[vf] = punct[i];
}
g << vf << '\n' ;
for ( int i = vf ; i >= 1 ; i--)
g << fixed << setprecision(6) << s[i].x << " " << s[i].y << '\n';
}