Pagini recente » Cod sursa (job #890013) | Cod sursa (job #771192) | Cod sursa (job #2230542) | Cod sursa (job #876537) | Cod sursa (job #3198063)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <climits>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int N_MAX = 120001;
int n, p, py = INT_MAX, l;
int v[N_MAX], r[N_MAX];
double x[N_MAX], y[N_MAX];
bool cmp(const int& p1, const int& p2){
return ((y[p1] - y[p]) * (x[p2] - x[p])) > ((y[p2] - y[p]) * (x[p1] - x[p]));
}
inline double semn(int p1, int p2, int p3){ /// formula la determinant
return (x[p2] - x[p1]) * (y[p3] - y[p1]) - (x[p3] - x[p1]) * (y[p2] - y[p1]);
}
int main()
{
f >> n;
for(int i = 1; i <= n; ++i){
v[i] = i;
f >> x[i] >> y[i];
if(py > y[i]){
p = i;
py = y[i];
}
}
swap(v[p], v[1]); /// pun p pe primul loc
sort(v + 2, v + n + 1, cmp);
r[++l] = p, r[++l] = v[2];
for(int i = 3; i <= n; ++i){
while(semn(r[l-1], r[l], v[i]) > 0)
l--;
r[++l] = v[i];
}
g << l << '\n';
for(int i = l; i > 0; --i)
g << fixed << setprecision(12) << x[r[i]] << ' ' << setprecision(12) << y[r[i]] << '\n';
return 0;
}