Pagini recente » Cod sursa (job #3038205) | Cod sursa (job #393761) | Cod sursa (job #70365) | Cod sursa (job #713411) | Cod sursa (job #2527164)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define INF 1000000010
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n, i, poz, k, stv[130000];
double minx, miny;
/*
Ideea este sa sortam toate punctele dupa punctul cel mai mic ( dupa x si apoi dupa y)
Le sortam in functie de fata de punctul cel mai mic
*/
struct coord
{
double x, y;
};
coord v[130000],aux;
int scoate(double x1, double y1, double x2, double y2, double x3, double y3)
{
long double x = ((long double)x2-x1)*(y3-y1)-(x3-x1)*(y2-y1);
if(x >= 0)
return 1; // sens trigonometric sau coliniar
return 0;
}
int cmp(coord a, coord b)
{
return (a.x * b.y) > (a.y * b.x);
}
int main()
{
cin >> n;
minx = INF;
miny = INF;
v[0].x = INF;
v[0].y = INF;
poz = 0;
for(i = 1 ; i <= n; i++) // il gasim pe cel mai mic, dupa x si dupa y
{
cin >> v[i].x >> v[i].y;
if(v[i].x < v[poz].x)
poz = i;
else if(v[i].x == v[poz].x && v[i].y < v[poz].y)
poz = i;
}
aux = v[poz], v[poz] = v[1], v[1] = aux; // spunem ca e primul
minx = v[1].x;
miny = v[1].y;
for(i=1 ; i <= n ; i++ )
v[i].x -= minx, v[i].y -= miny; // scadem din toate minim, ca sa avem valori mai mici, asa e mai usor
sort(v + 2, v + n + 1, cmp); // sortam dupa
stv[1] = 1; // punem un numar in stiva
stv[2] = 2;
k = 2;
for(i=3; i<=n; i++)
{
while( k>=2 &&
scoate( v[i].x, v[i].y, v[stv[k]].x, v[stv[k]].y, v[stv[k-1]].x, v[stv[k-1]].y) )
k--; // scoatem cat timp
stv[++k] = i;
}
cout << k << '\n';
cout << fixed;
for(i=1; i<= k; i++)
cout << setprecision(6) << v[stv[i]].x + minx << ' ' <<
v[stv[i]].y + miny << '\n'; // adaugam minimul la final
return 0;
}