Pagini recente » Cod sursa (job #1202347) | Cod sursa (job #3175527) | Cod sursa (job #3192825) | Cod sursa (job #2926752) | Cod sursa (job #3216313)
#include <fstream>
#include <iomanip>
#include <algorithm>
#define s second
#define f first
const int NMAX=120000+5;
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
typedef long double ld;
typedef pair<ld, ld> pld;
ld det(pld, pld, pld);
bool cmp(pld, pld);
pld v[NMAX], st[NMAX];
int n;
ld aria;
signed main()
{
int i, poz=1, cnt=0;
pld minim={1e9, 1e9};
cin>>n;
for(i=1; i<=n; i++)
{
cin>>v[i].f>>v[i].s;
if(minim.s>v[i].s)
{
minim=v[i];
poz=i;
}
else if(minim.s==v[i].s && minim.f>v[i].f)
{
minim=v[i];
poz=i;
}
}
swap(v[poz], v[1]);
sort(v+2, v+n+1, cmp);
st[++cnt]=v[1];
st[++cnt]=v[2];
for(i=3; i<=n; i++)
{
while(cnt>=2 && det(v[i], st[cnt-1], st[cnt])>0)
cnt--;
st[++cnt]=v[i];
}
cout<<cnt<<'\n';
for(i=cnt; i>=1; i--) cout<<fixed<<setprecision(6)<<st[i].f<<' '<<st[i].s<<'\n';
return 0;
}
bool cmp(pld a, pld b)
{
return det(b, v[1], a)<0;
}
ld det(pld a, pld b, pld c)
{
return a.f*(b.s-c.s)-a.s*(b.f-c.f)+(b.f*c.s-b.s*c.f);
}