Pagini recente » Cod sursa (job #862506) | Cod sursa (job #1602989) | Cod sursa (job #303707) | Cod sursa (job #2018834) | Cod sursa (job #1386871)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int N, top;
struct puncte
{
double x, y;
};
puncte V[120005], ST[120005];
double cross_panta(puncte A, puncte B, puncte C)
{
return (B.y - A.y) * (C.x - A.x) - (C.y - A.y) * (B.x - A.x);
}
bool cmp(puncte p1, puncte p2)
{
return cross_panta(V[1], p1, p2) < 0;
}
void sort_points()
{
int pos = 1;
for (int i = 2; i <= N; ++i)
if (V[i].x < V[pos].x || (V[i].x == V[pos].x && V[i].y < V[pos].y))
pos = i;
swap(V[1], V[pos]);
sort(V + 2, V + N + 1, cmp);
}
void convex_hull()
{
sort_points();
ST[1] = V[1];
ST[2] = V[2];
top = 2;
for (int i = 3; i <= N; ++i)
{
while (top >= 2 && cross_panta(ST[top - 1], ST[top], V[i]) > 0)
--top;
ST[++top] = V[i];
}
}
int main()
{
fin >> N;
for (int i = 1; i <= N; ++i)
fin >> V[i].x >> V[i].y;
convex_hull();
fout << top << '\n';
for (int i = 1; i <= top; ++i)
fout << fixed << setprecision(12) << ST[i].x << ' ' << ST[i].y << '\n';
fin.close();
fout.close();
return 0;
}