Pagini recente » Cod sursa (job #1939005) | Cod sursa (job #335224) | Cod sursa (job #551981) | Cod sursa (job #1729301) | Cod sursa (job #1611588)
#include <algorithm>
#include <fstream>
#include <iomanip>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
#define N 120001
#define XY 1000000001
int n;
double X[N], Y[N];
int V[N];
int stiva[N], nstiva = 0;
double produs_vectorial(int a, int b, int c)
{
return (X[b] - X[a]) * (Y[c] - Y[a]) - (Y[b] - Y[a]) * (X[c] - X[a]);
}
bool cmp(int v1, int v2)
{
return produs_vectorial(V[1], v1, v2) < 0;
}
int main()
{
in >> n;
for(int i = 1; i <= n; i++)
{
in >> X[i] >> Y[i];
V[i] = i;
}
int punct_initial = 1;
for(int i = 2; i <= n; i++)
if(X[V[i]] < X[V[punct_initial]])
punct_initial = i;
swap(V[1], V[punct_initial]);
sort(V + 2, V + n + 1, cmp);
stiva[++nstiva] = V[1];
stiva[++nstiva] = V[2];
for(int i = 3; i <= n; i++)
{
while(nstiva >= 2 && produs_vectorial(stiva[nstiva - 1], stiva[nstiva], V[i]) > 0)
nstiva--;
stiva[++nstiva] = V[i];
}
out << nstiva << '\n';
for(int i = nstiva; i >= 1; i--)
out << setprecision(12) << X[stiva[i]] << ' ' << Y[stiva[i]] << '\n';
return 0;
}