Pagini recente » Cod sursa (job #684303) | Cod sursa (job #2296877) | Cod sursa (job #227605) | Cod sursa (job #562535) | Cod sursa (job #3210254)
#include <iostream>
#include <fstream>
#include <cmath>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct
{
long double x;
long double y;
long double angle;
};
const int nmax = 125005;
int n;
punct puncte[nmax];
int hull[nmax];
int h; //inaltimea hull-ului -> ca sa stiu pe unde ma aflu
void citire()
{
f >> n;
for (int i = 0; i < n; i++)
{
f >> puncte[i].x >> puncte[i].y;
}
}
bool counter_clock(punct a, punct b, punct c)
{
return ((b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y)) < 0;
}
void graham()
{
hull[0] = 0;
hull[1] = 1;
h = 2;
for (int i = 2; i < n; i++)
{
while (h >= 2 && !counter_clock(puncte[hull[h - 2]], puncte[hull[h - 1]], puncte[i]))
{
h--;
}
hull[h] = i;
h++;
}
}
void solve()
{
for (int i = 1; i < n; i++)
{
if (puncte[i].y < puncte[0].y)
{
swap(puncte[0].y , puncte[i].y);
}
}
puncte[0].angle = 0;
for (int i = 1; i < n; i++)
{
puncte[i].angle = atan2(puncte[i].y - puncte[0].y, puncte[i].x - puncte[0].x);
}
sort(puncte + 1, puncte + n, [](punct a, punct b) {
return a.angle < b.angle;
});
/*
for (int i = 0; i < n; i++)
{
g << puncte[i].x << ' ' << puncte[i].y << ' ' << puncte[i].angle << '\n';
}*/
graham();
g << h << '\n';
for (int i = 0; i < h; i++)
{
int indx = hull[i];
g << fixed << setprecision(12) << puncte[indx].x << ' ';
g << fixed << setprecision(12) << puncte[indx].y << ' ';
g << '\n';
}
}
int main()
{
citire();
solve();
}