Pagini recente » Cod sursa (job #1223533) | Cod sursa (job #193666) | Cod sursa (job #1022849) | Cod sursa (job #1314618) | Cod sursa (job #1884783)
#include <cstdio>
#include <algorithm>
#include <utility>
using namespace std;
int n;
pair<double, double> puncte[120005];
pair<double, double> solutie[120005];
pair<int, int> fir;
double determinant(pair<int, int> x, pair<int, int> y, pair<int, int> z)
{
return (y.first - x.first) * (z.second - x.second) - (y.second - x.second) * (z.first - x.first);
}
bool compare(pair<int, int> x, pair<int, int> y)
{
return (determinant(fir, x, y) > 0);
}
void citire()
{
scanf("%d", &n);
double tmp1, tmp2;
for(int i = 0; i < n; i++)
{
scanf("%lf %lf", &tmp1, &tmp2);
puncte[i] = make_pair(tmp1, tmp2);
}
int minx = 0, miny = 0;
for(int i = 0; i < n; i++)
{
if(puncte[i].first < puncte[minx].first)
{
minx = i;
}
}
for(int i = 0; i < n; i++)
{
if(puncte[i].first == puncte[minx].first && puncte[i].second < puncte[miny].second)
{
miny = i;
}
}
swap(puncte[0], puncte[miny]);
fir = puncte[0];
}
void solve()
{
sort(puncte + 1, puncte + n, compare);
solutie[0] = puncte[0];
solutie[1] = puncte[1];
int k = 2;
for(int j = 2; j < n; j++, k++)
{
while(determinant(puncte[k - 2], puncte[k - 1], puncte[j]) < 0 && k > 0)
{
k--;
}
puncte[k] = puncte[j];
}
printf("%d\n", k);
printf("%lf %lf\n", puncte[0].first, puncte[0].second);
for(int i = 1; i < k; i++)
{
printf("%lf %lf\n", puncte[i].first, puncte[i].second);
}
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
citire();
solve();
return 0;
}