Pagini recente » Cod sursa (job #1137446) | Cod sursa (job #1122086) | Cod sursa (job #933155) | Cod sursa (job #1144506) | Cod sursa (job #1703322)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define pct pair<double,double>
using namespace std;
ifstream si("infasuratoare.in");
ofstream so("infasuratoare.out");
const int NMAX=120005;
pct v[NMAX];
double det(pct a,pct b,pct c)
{
return ((a.first-b.first)*(a.second-c.second)-(a.first-c.first)*(a.second-b.second));
}
bool comp(pct a,pct b)
{
return (det(v[0],a,b)<0);
}
pct sol[NMAX];
int main()
{
int n;
si>>n;
int i;
for(i=0;i<n;++i)
{
si>>v[i].first>>v[i].second;
}
for(i=1;i<n;++i)
{
if(v[i]<v[0])
swap(v[i],v[0]);
}
sort(v,v+n,comp);
int nr=0;
for(i=0;i<n;++i)
{
if(nr<2)
{
sol[nr]=v[i];
++nr;
}
else
{
while(nr>=2&&det(sol[nr-2],sol[nr-1],v[i])>0) nr--;
sol[nr]=v[i];
++nr;
}
}
so<<nr<<'\n';
so<<fixed;
for(i=nr-1;i>=0;--i)
so<<setprecision(6)<<sol[i].first<<' '<<sol[i].second<<'\n';
return 0;
}