Pagini recente » Cod sursa (job #3203594) | Cod sursa (job #1053410) | Cod sursa (job #3171822) | Cod sursa (job #1833305) | Cod sursa (job #429785)
Cod sursa(job #429785)
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
#define NMAX 10000
vector <pair <double, double> > puncte;
vector <pair <int, double> > pante;
long st[NMAX], n;
double a, b;
int cmpf(pair <double, double> a, pair <double, double> b)
{
if (a.first < b.first)
return 1;
else
if (a.first == b.first)
return a.second < b.second;
return 0;
}
int cmpf2(pair <int, double> a, pair <int, double> b)
{
return a.second < b.second;
}
double panta(long i, long j)
{
return (double)(puncte[j].second - puncte[i].second) / (puncte[j].first - puncte[i].first);
}
double semn(long i, long j, long k)
{
return (double)puncte[i].first * puncte[j].second + puncte[j].first * puncte[k].second + puncte[k].first * puncte[i].second - puncte[i].second * puncte[j].first - puncte[j].second * puncte[k].first - puncte[k].second * puncte[i].first;
}
int main()
{
freopen ("infasuratoare.in", "rt", stdin);
freopen ("infasuratoare.out", "wt", stdout);
scanf("%ld", &n);
for (long i = 0; i < n; ++i)
{
scanf("%lf %lf", &a, &b);
puncte.push_back(make_pair(a, b));
}
sort(puncte.begin(), puncte.end(), cmpf);
for (long i = 1; i < n; ++i)
pante.push_back(make_pair(i, panta(0, i)));
sort(pante.begin(), pante.end(), cmpf2);
st[0] = 2;
st[1] = 0;
st[2] = pante[0].first;
for (long i = 1; i < n - 1; ++i)
{
while (semn(st[st[0] - 1], st[st[0]], pante[i].first) < 0)
--st[0];
st[++st[0]] = pante[i].first;
}
printf("%ld\n", st[0]);
for (long i = 1; i <= st[0]; ++i)
printf("%lf %lf\n", puncte[st[i]].first, puncte[st[i]].second);
return 0;
}