Pagini recente » Cod sursa (job #3241768) | Cod sursa (job #1744928) | Cod sursa (job #3172607) | Cod sursa (job #79531) | Cod sursa (job #1642689)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int Nmax = 120005;
int n;
pair <double,double> a[Nmax], st[Nmax];
double sign( pair < double, double > a1, pair < double, double > b, pair < double, double > c)
{
return a1.first*b.second + b.first*c.second + c.first*a1.second - a1.second*b.first - b.second*c.first - c.second*a1.first;
}
bool crt(pair < double, double > a1, pair < double, double > b)
{
return sign(a[1], a1, b) > 0;
}
int main()
{
int m = 1, vf = 2;
f>>n;
for(int i = 1; i <= n; i++) f>>a[i].first>>a[i].second;
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[m],a[1]);
sort(a+2,a+1+n,crt);
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];
}
g<<vf<<'\n';
for(int i = 1; i <= vf; i++) g<<fixed<<setprecision(9)<<st[i].first<<' '<<st[i].second<<'\n';
return 0;
}