Pagini recente » Cod sursa (job #1397923) | Cod sursa (job #1786845) | Cod sursa (job #463914) | Cod sursa (job #2068792) | Cod sursa (job #1997340)
#include <bits/stdc++.h>
using namespace std;
struct punct
{
long double x, y;
} v[120005];
vector<punct> solve;
long double determinant (int x1, int y1, int x2, int y2, int x3, int y3)
{
return x1*y2 + x2*y3 + x3*y1 - y1*x2 - y2*x3 - y3*x1;
}
class cmp
{
public:
bool operator () (const punct &a, const punct &b) const
{
if (determinant(v[0].x, v[0].y, a.x, a.y, b.x, b.y)>0) return 1;
if (determinant(v[0].x, v[0].y, a.x, a.y, b.x, b.y)<0) return 0;
return a.x < b.x;
}
};
int main()
{
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
int n;
fin >> n;
fin >> v[0].x >> v[0].y;
for (int i = 1; i<n; ++i)
{
fin >> v[i].x >> v[i].y;
if (v[i].x < v[0].x || (v[i].x==v[0].x && v[i].y < v[0].y))
swap (v[0], v[i]);
}
v[n] = v[0];
sort (v+1, v+n, cmp());
solve.push_back(v[0]);
for (int i = 1; i<=n; ++i)
{
bool verif = 1;
while (solve.size()>=2 && verif)
{
verif = 0;
punct alfa = solve.back();
solve.pop_back();
if (determinant(solve.back().x, solve.back().y, alfa.x, alfa.y, v[i].x, v[i].y) <= 0)
verif = 1;
else solve.push_back(alfa);
}
solve.push_back(v[i]);
}
solve.pop_back();
for (auto x:solve)
fout << setprecision(8) << fixed << x.x << " " << x.y << '\n';
return 0;
}