Pagini recente » Cod sursa (job #1327332) | Cod sursa (job #1112195) | Cod sursa (job #286810) | Cod sursa (job #189120) | Cod sursa (job #3226148)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
struct punct
{
double x, y;
};
bool cmp(punct p1, punct p2)
{
if (p1.x == p2.x)
{
return (p1.y < p2.y);
}
return (p1.x < p2.x);
}
double aria(punct a, punct b, punct c)
{
return (a.x - b.x) * (a.y + b.y) + (b.x - c.x) * (b.y + c.y) + (c.x - a.x) * (c.y + a.y);
}
int main()
{
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int n;
in >> n;
vector <punct> v(n);
for (int i = 0; i < n; i++)
{
in >> v[i].x >> v[i].y;
}
sort(v.begin(), v.end(), cmp);
vector <punct> stiva(n + 1);
int vf = 0;
for (int i = 0; i < n; i++)
{
while (vf > 1 && aria(stiva[vf-1], stiva[vf], v[i]) < 0)
{
vf--;
}
stiva[++vf] = v[i];
}
for (int i = n - 2; i > 0; i--)
{
while (vf > 1 && aria(stiva[vf-1], stiva[vf], v[i]) < 0)
{
vf--;
}
stiva[++vf] = v[i];
}
out << vf << "\n";
for (int i = 1; i <= vf; i++)
{
out << stiva[i].x << " " << stiva[i].y << "\n";
}
in.close();
out.close();
return 0;
}