Pagini recente » Cod sursa (job #828598) | Cod sursa (job #2804057) | Cod sursa (job #739435) | Cod sursa (job #1053226) | Cod sursa (job #1595026)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
pair <double,double> v[120001],st[120001];
int n,i,k,Min;
bool determ(pair<double, double> A, pair<double,double> B, pair<double, double> C)
{
if (A.first*B.second + B.first*C.second + A.second*C.first - C.first*B.second - A.first*C.second - A.second*B.first > 0)
return true;
else
return false;
}
int main()
{
fin>>n;
for (i=1;i<=n;i++)
{
fin>>v[i].first>>v[i].second;
}
sort(v+1,v+1+n);
st[1]=v[1];
st[2]=v[2];
k=2;
for (i=3;i<=n;i++)
{
while (k>1 && !determ(st[k-1],st[k],v[i]))
k--;
k++;
st[k]=v[i];
}
Min=k;
for (i=n-1;i>=1;i--)
{
while (k>Min && !determ(st[k-1],st[k],v[i]))
k--;
k++;
st[k]=v[i];
}
fout<<k-1<<"\n";
fout<<setprecision(6)<<fixed;
for (i=1;i<k;i++)
{
fout<<st[i].first<<" "<<st[i].second<<"\n";
}
return 0;
}