Pagini recente » Cod sursa (job #2480213) | Cod sursa (job #849233) | Cod sursa (job #1435107) | Cod sursa (job #904409) | Cod sursa (job #2339484)
#include <bits/stdc++.h>
#define ld long double
using namespace std;
ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");
const int NMAX = 120005;
int n;
pair <ld, ld> x[NMAX];
pair <ld, ld> sus[NMAX], jos[NMAX];
int kSus, kJos;
ld dist(pair <ld, ld> A, pair <ld, ld> B)
{
return sqrt(abs(A.first - B.first) * abs(A.first - B.first) + abs(A.second - B.second) * abs(A.second - B.second));
}
long double panta(pair <ld, ld> A, pair <ld, ld> B)
{
long double ret = abs(A.first - B.first) / dist(A, B);
if (B.second > A.second)
ret = 1 + 1 - ret;
return ret;
}
int main()
{
fi >> n;
for (int i = 1; i <= n; i++)
{
fi >> x[i].first >> x[i].second;
}
sort(x + 1, x + n + 1);
jos[++kJos] = x[1];
sus[++kSus] = x[1];
for (int i = 2; i <= n; i++)
{
/*if (x[i].first == 10 && x[i].second == -3)
{
if (panta(x[1], x[i]) > panta(x[1], x[n]))
cout << "SUS";
else
cout << "JOS";
}*/
if (panta(x[1], x[i]) > panta(x[1], x[n]) || i == n) // sus
{
while (kSus > 1 && panta(sus[kSus - 1], sus[kSus]) < panta(sus[kSus - 1], x[i]))
kSus--;
sus[++kSus] = x[i];
//cout << x[i].first << ", " << x[i].second << " este sus cu panta: " << panta(x[1], x[i]) <<"\n";
}
if (panta(x[1], x[i]) < panta(x[1], x[n]) || i == n) // jos
{
while (kJos > 1 && panta(jos[kJos - 1], jos[kJos]) > panta(jos[kJos - 1], x[i]))
kJos--;
jos[++kJos] = x[i];
//cout << x[i].first << ", " << x[i].second << " este jos cu panta: " << panta(x[1], x[i]) << "\n";
}
}
fo << kSus + kJos - 2 << "\n";
for (int i = 2; i <= kJos; i++)
fo << fixed << setprecision(15) << jos[i].first << " " << jos[i].second << "\n";
for (int i = kSus - 1; i >= 1; i--)
fo << fixed << setprecision(15) << sus[i].first << " " << sus[i].second << "\n";
return 0;
}