Pagini recente » Cod sursa (job #2341647) | Cod sursa (job #2653293) | Cod sursa (job #3004499) | Cod sursa (job #1820682) | Cod sursa (job #2545750)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct point
{
double x, y;
friend istream& operator>>(istream& in, point& p)
{
p = point();
in >> p.x >> p.y;
return in;
}
friend ostream& operator<<(ostream& out, point& p)
{
out << p.x << " " << p.y;
return out;
}
};
vector<point> V = vector<point>();
int n;
double slope(point p1, point p2)
{
return (p1.y - p2.y) / (p1.x - p2.x);
}
double ccw(point p1, point p2, point p3)
{
return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}
vector<point> Graham(vector<point> input, point left)
{
vector<point> result = vector<point>();
result.push_back(left);
result.push_back(input[0]);
input.erase(input.begin());
for (auto it : input)
{
while (result.size() > 1 && ccw(result[result.size() - 2], result.back(), it) < 0)
result.pop_back();
result.push_back(it);
}
return result;
}
int main()
{
in >> n;
point p;
for (int i = 0; i < n; i++)
{
in >> p;
V.push_back(p);
}
point chosen_left = V[0];
int i = 0, pos = 0;
for (auto it : V)
{
if (it.x < chosen_left.x || it.x == chosen_left.x && it.y < chosen_left.y)
{
chosen_left = it;
pos = i;
}
i++;
}
V.erase(V.begin() + pos);
sort(V.begin(), V.end(), [chosen_left](point p1, point p2) {return slope(p1, chosen_left) < slope(p2, chosen_left); });
auto result = Graham(V, chosen_left);
out << result.size() << "\n";
for (auto it : result)
out << setprecision(13) << it << "\n";
return 0;
}