Pagini recente » Cod sursa (job #2568734) | Cod sursa (job #2599287) | Cod sursa (job #1641262) | Cod sursa (job #2622296) | Cod sursa (job #2110623)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define Nmax 120005
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int N, j;
pair<double, double>p[Nmax];
pair<double, double>st[Nmax];
bool cmp(pair<double, double> a, pair<double, double> b)
{
if(a.first == b.first)return a.second < b.second;
return a.first < b.first;
}
double determ(pair<double, double> a, pair<double, double> b, pair<double, double>c)
{
return ((a.first - c.first)*(b.second - c.second) + (b.first - c.first)*(c.second - a.second));
}
int main()
{
fin >> N;
for(int i = 1; i <= N; i++)
fin >> p[i].first >> p[i].second;
sort(p + 1, p + N + 1, cmp);
st[1].first = p[1].first;
st[1].second = p[1].second;
j = 1;
for(int i = 2; i <= N; i++)
{
while(j > 1 && determ(st[j - 1], st[j], p[i]) > 0)
j--;
j++;
st[j].first = p[i].first;
st[j].second = p[i].second;
}
for(int i = N - 1; i >= 1; i--)
{
while(j > 1 && determ(st[j - 1], st[j], p[i]) > 0)
j--;
j++;
st[j] = p[i];
}
j--;
fout << j << '\n';
for(int i = j; i >= 1; i--)
fout << fixed << setprecision(6) << st[i].first << " " << st[i].second << '\n';
return 0;
}