Pagini recente » Cod sursa (job #293048) | Cod sursa (job #467054) | Cod sursa (job #2752212) | Cod sursa (job #3283630) | Cod sursa (job #2400515)
#include <bits/stdc++.h>
#define N 120005
using namespace std;
ifstream fin ("infasuratoareconvexa.in");
ofstream fout ("infasuratoareconvexa.out");
struct punct
{
double x, y;
};
int n;
int st[N], top;
punct a[N];
void Citire()
{
fin >> n;
for (int i = 1; i <= n; i++)
fin >> a[i].x >> a[i].y;
}
double prod_Vectorial(punct p, punct m, punct q)
{
double y1 = p.y - m.y;
double y2 = p.y - q.y;
double x1 = p.x - m.x;
double x2 = p.x - q.x;
return y2 * x1 - y1 * x2;
}
bool cmp(punct p, punct q)
{
return prod_Vectorial(a[1], p, q) > 0;
}
void Sorteaza()
{
int ind = 1;
for (int i = 2; i <= n; i++)
if (a[i].x < a[ind].x)
ind = i;
swap(a[1], a[ind]);
sort(a + 2, a + n + 1, cmp);
}
void Solve()
{
st[1] = 1;
st[2] = 2;
top = 2;
for (int i = 3; i <= n; i++)
{
while (top > 2 && prod_Vectorial(a[st[top - 1]], a[st[top]], a[i]) < 0)
top--;
st[++top] = i;
}
fout << top << "\n";
for (int i = 1; i <= top; i++)
fout << fixed << setprecision(9) << a[st[i]].x << " " << a[st[i]].y << "\n";
}
int main()
{
Citire();
Sorteaza();
Solve();
return 0;
}