Pagini recente » Cod sursa (job #1724395) | Cod sursa (job #212878) | Cod sursa (job #1957038) | Cod sursa (job #693369) | Cod sursa (job #2987635)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point
{
double x, y;
};
int n;
vector<point> points;
vector<point> s1, s2;
vector<point> rez;
int orientation(point a, point b, point c)
{
double v = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
if (v < 0)
{
return -1;
}
if (v > 0)
{
return 1;
}
return 0;
}
bool cw(point a, point b, point c, bool include_collinear)
{
int o = orientation(a, b, c);
return o < 0 || (o == 0 && include_collinear);
}
bool ccw(point a, point b, point c, bool include_collinear)
{
int o = orientation(a, b, c);
return o > 0 || (o == 0 && include_collinear);
}
bool cmp(point a, point b)
{
if (a.y == b.y)
{
return a.x < b.x;
}
return a.y < b.y;
}
void convex_hull(bool include_collinear = false)
{
sort(points.begin(), points.end(), cmp);
point p0 = points[0];
s1.push_back(p0);
for (int i = 1; i < (int)points.size(); i++)
{
while (s1.size() >= 2 && !ccw(s1[s1.size() - 2], s1.back(), points[i], include_collinear))
{
s1.pop_back();
}
s1.push_back(points[i]);
}
s2.push_back(p0);
for (int i = 1; i < (int)points.size(); i++)
{
while (s2.size() >= 2 && !cw(s2[s2.size() - 2], s2.back(), points[i], include_collinear))
{
s2.pop_back();
}
s2.push_back(points[i]);
}
if (include_collinear && s1.size() == points.size())
{
reverse(s1.begin(), s1.end());
rez = s1;
return;
}
s2.pop_back();
reverse(s2.begin(), s2.end());
s2.pop_back();
for (auto point : s1)
{
rez.push_back(point);
}
for (auto point : s2)
{
rez.push_back(point);
}
}
int main()
{
fin >> n;
for (int i = 1; i <= n; i++)
{
double x, y;
fin >> x >> y;
points.push_back({x, y});
}
convex_hull(true);
for (auto point : rez)
{
fout << fixed << setprecision(6) << point.x << ' ' << point.y << '\n';
}
return 0;
}