Pagini recente » Cod sursa (job #2884694) | Cod sursa (job #2293988) | Cod sursa (job #1440449) | Cod sursa (job #1985729) | Cod sursa (job #1571208)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int NMax = 120005;
pair <double, double> a[NMax], st[NMax];
int n, vf;
void Read()
{
f>>n;
for(int i = 1; i <= n; i++) f>>a[i].first>>a[i].second;
}
double Sign(pair <double, double> x, pair <double, double> y, pair <double, double> z)
{
return (x.first*y.second + y.first*z.second + z.first*x.second - x.second*y.first - y.second*z.first - z.second*x.first);
}
bool Crit(pair <double, double> x, pair <double, double> y)
{
return Sign(a[1],x,y) > 0;
}
void Solve()
{
int m = 1;
vf = 2;
for(int i = 1; i <= n; i++)
if(a[i].second < a[m].second || (a[i].second == a[m].second && a[i].first < a[m].first)) m = i;
swap(a[1],a[m]);
sort(a+2, a+n+1, Crit);
st[1] = a[1]; st[2] = a[2];
for(int i = 3; i <= n; i++)
{
while(vf >= 2 && Sign(st[vf-1],st[vf],a[i]) < 0) vf--;
st[++vf] = a[i];
}
}
void Print()
{
g<<vf<<'\n';
for(int i = 1; i <= vf; i++) g<<fixed<<setprecision(9)<<st[i].first<<' '<<st[i].second<<'\n';
}
int main()
{
Read();
Solve();
Print();
return 0;
}