Pagini recente » Cod sursa (job #2368968) | Cod sursa (job #1752619) | Cod sursa (job #2974414) | Cod sursa (job #755414) | Cod sursa (job #2403695)
#include <bits/stdc++.h>
#define N 120010
#define PI 3.141592653
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct punct
{
double x, y;
double unghi;
};
int n, k;
int st[N], top;
punct a[N], sol[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;
}
double dist(punct p, punct q)
{
return sqrt((p.x - q.x) * (p.x - q.x) + (p.y - q.y) * (p.y - q.y));
}
bool cmp(punct p, punct q)
{
if (!prod_Vectorial(a[1], p, q))
return dist(a[1], p) > dist(a[1], 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 || (a[i].x == a[ind].x && a[i].y < a[ind].y))
ind = i;
swap(a[1], a[ind]);
sort(a + 2, a + n + 1, cmp);
}
void Select()
{
for (int i = 2; i <= n; i++)
{
if (a[i].y == a[1].y)
a[i].unghi = 90;
else
{
a[i].unghi = atan2(a[i].x - a[1].x, a[i].y - a[1].y) * 180 / PI;
if (a[i].unghi < 0)
a[i].unghi *= -1;
else a[i].unghi = 180 - a[i].unghi;
}
}
double first_ang = a[2].unghi, last_ang = a[n].unghi;
int ind;
for (int i = 2; i <= n; i++)
if (a[i].unghi == first_ang)
ind = i;
for (int i = 2, j = ind; i < j; i++, j--)
{
punct aux = a[i];
a[i] = a[j];
a[j] = aux;
}
sol[++k] = a[1];
for (int i = 2; i <= n; i++)
{
if (a[i].unghi == first_ang || a[i].unghi == last_ang)
sol[++k] = a[i];
else if (a[i].unghi != a[i - 1].unghi)
sol[++k] = a[i];
}
}
void Solve()
{
st[1] = 1;
st[2] = 2;
top = 2;
for (int i = 3; i <= k; i++)
{
while (top > 2 && prod_Vectorial(sol[st[top - 1]], sol[st[top]], sol[i]) < 0)
top--;
st[++top] = i;
}
fout << top << "\n";
for (int i = 1; i <= top; i++)
fout << fixed << setprecision(9) << sol[st[i]].x << " " << sol[st[i]].y << "\n";
}
int main()
{
Citire();
Sorteaza();
Select();
Solve();
return 0;
}