Pagini recente » Cod sursa (job #3273159) | Cod sursa (job #3138179) | Cod sursa (job #1822862) | Cod sursa (job #1503699) | Cod sursa (job #2358146)
#include <fstream>
#include <iomanip>
#include <vector>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
enum Direction
{
Left,
Right
};
struct point
{
double x, y;
point() {};
point(double X, double Y) : x(X), y(Y) {};
friend istream &operator>> (istream &in, point &p)
{
in >> p.x >> p.y;
return in;
}
friend ostream &operator<< (ostream &out, point &p)
{
out << fixed << setprecision(6) << p.x << " " << p.y;
return out;
}
}P[120001];
int n;
auto slope = [](point a, point b) {return (a.y - b.y) / (a.x - b.x); };
auto turn_direction = [](point a, point b, point c) {return ((b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x) > 0 ? Left : Right); };
void swapp(point &a, point &b, double &sa, double &sb)
{
double aux = sa;
sa = sb;
sb = aux;
point ap = a;
a = b;
b = ap;
}
void sort_points()
{
double slopes[120001];
for (int i = 1; i < n; i++)
slopes[i] = slope(P[0], P[i]);
for (int i = 1; i < n; i++)
for (int j = i + 1; j < n; j++)
{
if (slopes[i] > 0)
{
if (slopes[j] > 0 && slopes[i] > slopes[j])
swapp(P[i], P[j], slopes[i], slopes[j]);
}
else
{
if (slopes[j] < 0 && slopes[i] > slopes[j] || slopes[j] > 0)
swapp(P[i], P[j], slopes[i], slopes[j]);
}
}
}
point s[120001];
int ks = 3;
void Graham()
{
s[0] = P[0];
s[1] = P[1];
s[2] = P[2];
for (int i = 3; i < n; i++)
{
while (turn_direction(s[ks - 2], s[ks - 1], P[i]) == Right)
ks--;
s[ks++] = P[i];
}
}
int main()
{
f >> n;
int lpos, dpos;
double minx = 1000000010, miny = 1000000010;
for (int i = 0; i < n; i++)
{
f >> P[i];
if (P[i].x < minx)
minx = P[i].x, lpos = i;
else if (P[i].x == minx)
lpos = -1;
if (P[i].y < miny)
miny = P[i].y, dpos = i;
else if (P[i].y == miny)
dpos = -1;
}
lpos = (lpos != -1 ? lpos : dpos);
if (lpos == -1) return 0;
point aux = P[0];
P[0] = P[lpos];
P[lpos] = aux;
sort_points();
Graham();
g << ks << "\n";
for (int i = 0; i < ks; i++)
g << s[i] << "\n";
return 0;
}