Pagini recente » Cod sursa (job #2940559) | Cod sursa (job #385707) | Cod sursa (job #1164349) | Cod sursa (job #349355) | Cod sursa (job #3227451)
#include <algorithm>
#include <cmath>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <stack>
#include <vector>
#include <immintrin.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point
{
long double x, y, angle;
point(long double _x = 0, long double _y = 0, long double _angle = 0)
: x(_x), y(_y), angle(_angle) {}
} s;
// Formula se deduce din coordonata pe axa Oz
// a unui produs vectorial, anume P1P2 x P1P3.
inline 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;
}
// Folosit la determinarea punctului cel mai din
// stânga-jos. Apelul min_compare ar da eroare
// altfel.
inline 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.
inline bool pcompare2(point& p1, point& p2)
{
return atan2(p1.y, p1.x) < atan2(p2.y, p2.x);
}
inline bool acompare(point& p1, point& p2)
{
return p1.angle < p2.angle;
}
vector<point> graham_scan(vector<point>& ps)
{
s = *min_element(ps.begin(), ps.end(), pcompare1);
// 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ă.
for(auto& p : ps)
p.angle = atan2(p.y - s.y, p.x - s.x);
// E mai rapid să memorăm unghiul în puncte,
// decât să îl calculăm la fiecare comparație.
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;
}