Pagini recente » Cod sursa (job #2240255) | Cod sursa (job #592170) | Cod sursa (job #738666) | Cod sursa (job #2080341) | Cod sursa (job #3227427)
#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 pt
{
double x, y;
friend bool operator==(const pt& p1, const pt& p2)
{
return p1.x == p2.x && p1.y == p2.y;
}
pt(double _x = 0, double _y = 0)
: x(_x), y(_y) {}
} s;
pt start(vector<pt>& ps)
{
pt res(100000.0, 100000.0);
for(auto& p : ps)
if(p.y < res.y || (p.y == res.y && p.x < res.x))
res = p;
return res;
}
double cos(pt p)
{
return (p.x - s.x) / (p.y - s.y);
}
bool right_turn(pt p1, pt p2, pt p3)
{
return ((p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x)) < 0;
}
deque<pt> graham_scan(vector<pt>& ps)
{
s = start(ps);
auto cos_sort = [](pt a, pt b)
{
return cos(a) > cos(b);
};
sort(ps.begin(), ps.end(), cos_sort);
deque<pt> dq;
for(auto& p : ps)
{
dq.push_back(p);
if(dq.size() >= 3)
{
while(right_turn(dq[dq.size() - 3], dq[dq.size() - 2], dq[dq.size() - 1]))
{
pt last = dq[dq.size() - 1];
dq.pop_back();
dq.pop_back();
dq.push_back(last);
if(dq.size() < 3)
break;
}
}
}
return dq;
}
int main()
{
int n;
vector<pt> ps;
fin >> n;
for(int i = 1; i <= n; i++)
{
double x, y;
fin >> x >> y;
ps.push_back(pt(x, y));
}
deque<pt> result = graham_scan(ps);
for(auto& p : result)
fout << fixed << setprecision(6) << p.x << ' ' << p.y << '\n';
return 0;
}