Pagini recente » Cod sursa (job #2252588) | Cod sursa (job #298191) | Cod sursa (job #2998951) | Cod sursa (job #1810998) | Cod sursa (job #3266260)
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct point
{
double x;
double y;
};
point p[120001];
vector<point> stiva;
int n;
int cross_prod(point a, point b, point c)
{
double area = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
if (area < 0)
{
return -1; /// CA is turned clockwise over BA
}
else if (area == 0)
{
return 0; /// CA is colinear with BA
}
else if (area > 0)
{
return 1; /// CA is turned counter clockwise over BA
/// this is what we need here
}
}
bool cmp(point a, point b)
{
return cross_prod(p[1], a, b) > 0;
}
void convex_hull()
{
int minpos = 1;
for (int i = 1; i <= n; i ++)
{
if (p[minpos].y > p[i].y)
{
minpos = i;
}
else if (p[minpos].y == p[i].y)
{
if (p[minpos].x > p[i].x)
{
minpos = i;
}
}
}
swap(p[minpos], p[1]);
sort(p + 2, p + n + 1, cmp);
// for (int i = 1; i <= n; i ++)
// {
// cout << p[i].x << " " << p[i].y << "\n";
// }
int top = 0;
stiva.push_back(p[1]);
stiva.push_back(p[2]);
top ++;
for (int i = 3; i <= n; i ++)
{
if (cross_prod(stiva[top - 1], stiva[top], p[i]) >= 0 || top < 1)
{
top ++;
stiva.push_back(p[i]);
}
else
{
while (cross_prod(stiva[top - 1], stiva[top], p[i]) == -1)
{
top --;
stiva.pop_back();
}
top ++;
stiva.push_back(p[i]);
}
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++)
{
cin >> p[i].x >> p[i].y;
}
convex_hull();
cout << stiva.size() << "\n";
cout << fixed;
for (int i = 0; i < stiva.size(); i ++)
{
cout << setprecision(6) << stiva[i].x << " " << stiva[i].y << "\n";
}
return 0;
}