Pagini recente » Cod sursa (job #1174235) | Cod sursa (job #2506968) | Cod sursa (job #1549499) | Cod sursa (job #2286961) | Cod sursa (job #1265985)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n, i, x, s;
pair <double, double> A[12010], sol[12010];
double det(const pair<double, double> &a, const pair<double, double> &b, const pair<double, double> &c) {
return (b.first-a.first) * (c.second-a.second) - (c.first-a.first) * (b.second-a.second);
}
int cmp(const pair <double, double> &a, const pair< double, double> &b){
return det(A[1], a, b) > 0;
}
int main()
{
fin >> n;
for(i = 1; i <= n; i ++)
fin >> A[i].first >> A[i].second;
int x = 1;
for(i = 1; i <= n; i ++)
if(A[x] > A[i])
x = i;
pair < double, double > aux = A[1];
A[1] = A[x];
A[x] = aux;
sort(A + 2, A + n + 1, cmp);
sol[1] = A[1];
sol[2] = A[2];
s = 2;
for(i = 3; i <= n; i ++){
while( s >= 2 && det(sol[s - 1], sol[s], A[i]) <= 0)
s --;
sol[++s] = A[i];
}
fout << s << '\n';
for(i = 1; i <= s; i ++)
fout << setprecision(9) << fixed << sol[i].first << " " << sol[i].second << '\n';
return 0;
}