Pagini recente » Cod sursa (job #674496) | Cod sursa (job #310975) | Cod sursa (job #1430838) | Cod sursa (job #772921) | Cod sursa (job #3227447)
#include <algorithm>
#include <cmath>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point
{
long double x, y;
point(long double _x = 0, long double _y = 0)
: x(_x), y(_y) {}
} s;
// Folosit la determinarea punctului cel mai din
// stânga-jos. Apelul min_compare ar da eroare
// altfel.
bool pcompare1(point& p1, point& p2)
{
if(p1.y != p2.y)
return p1.y < p2.y;
return p1.x < p2.x;
}
// Sortare trigonometrică, cerută de problemă.
// Nu se pot afișa punctele în orice ordine.
bool pcompare2(point& p1, point& p2)
{
return atan2(p1.y, p1.x) < atan2(p2.y, p2.x);
}
// p.y - s.y și p.x - s.y sunt coordonatele
// vectorului SPi, după al cărui unghi se
// sortează. Funcția atan2 dă unghiul dintre
// vectorul cu coordonatele (y, x) și abscisă.
bool acompare(point p1, point p2)
{
long double a1 = atan2(p1.y - s.y, p1.x - s.x);
long double a2 = atan2(p2.y - s.y, p2.x - s.x);
return a1 < a2;
}
// Formula se deduce din coordonata pe axa Oz
// a unui produs vectorial, anume P1P2 x P1P3.
bool right(point p1, point p2, point p3)
{
return ((p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x)) < 0;
}
vector<point> graham_scan(vector<point>& ps)
{
s = *min_element(ps.begin(), ps.end(), pcompare1);
sort(ps.begin(), ps.end(), acompare);
vector<point> r;
for(auto& p : ps)
{
if(r.size() >= 2)
while(right(r[r.size() - 2], r[r.size() - 1], p))
{
r.pop_back();
if(r.size() < 2)
break;
}
r.push_back(p);
}
sort(r.begin(), r.end(), pcompare2);
return r;
}
int main()
{
int n;
vector<point> ps;
fin >> n;
for(int i = 1; i <= n; i++)
{
long double x, y;
fin >> x >> y;
ps.push_back(point(x, y));
}
vector<point> result = graham_scan(ps);
fout << result.size() << '\n';
for(const auto& p : result)
fout << fixed << setprecision(6) << p.x << ' ' << p.y << '\n';
return 0;
}