Pagini recente » Cod sursa (job #2534750) | Cod sursa (job #541786) | Cod sursa (job #1824865) | Cod sursa (job #40349) | Cod sursa (job #2987609)
#include <bits/stdc++.h>
using namespace std;
double INF = 1000000004;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
struct point
{
double x, y;
};
point p0;
vector<point> points;
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 ccw(point a, point b, point c, bool include_collinear)
{
int o = orientation(a, b, c);
return o > 0 || (include_collinear && o == 0);
}
bool collinear(point a, point b, point c)
{
return orientation(a, b, c) == 0;
}
double dist(point a, point b)
{
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
bool cmp(point a, point b)
{
if (orientation(p0, a, b) == 0)
{
return dist(p0, a) < dist(p0, b);
}
return orientation(p0, a, b) > 0;
}
void convex_hull(bool include_collinear = false)
{
p0 = {INF, INF};
for (auto point : points)
{
if (point.y < p0.y)
{
p0 = point;
}
else if (point.y == p0.y && point.x < p0.x)
{
p0 = point;
}
}
sort(points.begin(), points.end(), cmp);
if (include_collinear)
{
int i = (int)points.size() - 1;
while (i >= 0 && collinear(p0, points[i], points.back()))
{
i--;
}
reverse(points.begin() + i + 1, points.end());
}
for (int i = 0; i < (int)points.size(); i++)
{
while (rez.size() >= 2 && !ccw(rez[rez.size() - 2], rez.back(), points[i], include_collinear))
{
rez.pop_back();
}
rez.push_back(points[i]);
}
}
int main()
{
fin >> n;
for (int i = 1; i <= n; i++)
{
double x, y;
fin >> x >> y;
points.push_back({x, y});
}
convex_hull();
fout << rez.size() << '\n';
for (auto point : rez)
{
fout << fixed << setprecision(6) << point.x << ' ' << point.y << '\n';
}
return 0;
}