Pagini recente » Cod sursa (job #978818) | Cod sursa (job #1290447) | Cod sursa (job #867639) | Cod sursa (job #1433917) | Cod sursa (job #3245816)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct punct{
double x, y;
int parte;
}puncte[120005];
int st[120005];
bool cmp(punct a, punct b) {
if (a.x != b.x)
return a.x < b.x;
return a.y < b.y;
}
double arie(punct A, punct B, punct C) {
return A.x * B.y + B.x * C.y + C.x * A.y - B.y * C.x - C.y * A.x - A.y * B.x;
}
int main()
{
int n;
in >> n;
for (int i = 1; i <= n; i++)
in >> puncte[i].x >> puncte[i].y;
sort(puncte + 1, puncte + n + 1, cmp);
punct jos = puncte[1];
punct sus = puncte[n];
for (int i = 2; i < n; i++) {
if (arie(jos, sus, puncte[i]) < 0)
puncte[i].parte = 1;
else
puncte[i].parte = 2;
}
int k = 1;
st[k] = 1;
for (int i = 2; i <= n; i++)
if (puncte[i].parte == 1 || puncte[i].parte == 0) {
while (k > 1 && arie(puncte[st[k - 1]], puncte[st[k]], puncte[i]) < 0)
k--;
k++;
st[k] = i;
}
int ck = k;
for (int i = n - 1; i >= 1; i--)
if (puncte[i].parte == 2 || puncte[i].parte == 0) {
while (k > ck && arie(puncte[st[k - 1]], puncte[st[k]], puncte[i]) < 0)
k--;
k++;
st[k] = i;
}
out << k - 1 << "\n";
for (int i = 1; i < k; i++)
out << fixed << setprecision(6) << puncte[i].x << " " << puncte[i].y << "\n";
return 0;
}