Pagini recente » Cod sursa (job #1499705) | Cod sursa (job #2082461) | Cod sursa (job #1598511) | Cod sursa (job #1794082) | Cod sursa (job #2377176)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int Nmax = 130005;
int n, k;
struct Punct
{
double x, y;
};
Punct v[Nmax], s[Nmax];
double Det(const Punct &a, const Punct &b, const Punct &c)
{
return (b.x - a.x) *(c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
inline bool CMP(const Punct &a,const Punct &b)
{
return Det(v[1], a, b) > 0;
}
void Read()
{
int i;
fin >> n;
for (i = 1; i <= n; i++)
fin >> v[i].x >> v[i].y;
fin.close();
}
void Do()
{
int i, j, p;
p = 1;
for (i = 2; i <= n; i++)
if (v[i].y < v[p].y || (v[i].y == v[p].y && v[i].x < v[i].x)) p = i;
swap(v[1], v[p]);
sort(v + 2, v + n + 1, CMP);
s[++k] = v[1];
s[++k] = v[2];
for (i = 3; i <= n; i++)
{
while (k >= 2 && Det(s[k-1], s[k], v[i]) < 0) k--;
s[++k]=v[i];
}
}
void Write()
{
int i;
fout << k << "\n";
for (i = 1; i <= k; i++)
fout << setprecision(9) << fixed << s[i].x << " " << s[i].y << "\n";
fout.close();
}
int main()
{
Read();
Do();
Write();
return 0;
}