Pagini recente » Cod sursa (job #2069819) | Cod sursa (job #954900) | Cod sursa (job #1037550) | Cod sursa (job #2335714) | Cod sursa (job #2000615)
#include<fstream>
#include<iomanip>
#include<algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
pair <double,double> stiva[120003],a[120005];
double b[120005];
int main()
{
int n,i,maxx=1000000003,maxy=1000000003,x,j,l=3;
fin>>n;
for(i=1;i<=n;i++)
{
fin>>a[i].first>>a[i].second;
if(a[i].first<maxx)
{
maxx=a[i].first;
maxy=a[i].second;
x=i;
}
else
if(a[i].first==maxx && a[i].second<maxy)
{
maxy=a[i].second;
x=i;
}
}
swap(a[1],a[x]);
stiva[1]=a[1];
for(i=2;i<n;i++)
for(j=i+1;j<=n;j++)
if(a[i].second==a[1].second && a[j].second==a[1].second)
{
if(a[j].first-a[1].first>a[i].first-a[1].first)
swap(a[i],a[j]);
}
else
if((a[i].second-a[1].second)*(a[j].first-a[1].first)>(a[j].second-a[1].second)*(a[i].first-a[1].first))
swap(a[i],a[j]);
stiva[2]=a[2];
i=3;
while(i<=n)
{
if(stiva[l-1].first*a[i].second+a[i].first*stiva[l-2].second+stiva[l-2].first*stiva[l-1].second-stiva[l-2].first*a[i].second-stiva[l-1].first*stiva[l-2].second-a[i].first*stiva[l-1].second>0)
{
stiva[l].first=a[i].first;
stiva[l].second=a[i].second;
l++;
}
else
if(stiva[l-1].first*a[i].second+a[i].first*stiva[l-2].second+stiva[l-2].first*stiva[l-1].second-stiva[l-2].first*a[i].second-stiva[l-1].first*stiva[l-2].second-a[i].first*stiva[l-1].second<0 && l-1>2)
{
i--;
l--;
}
i++;
}
stiva[l]=stiva[1];
fout<<l-1<<'\n';
for(i=2;i<=l;i++)
fout<<fixed<<setprecision(6)<<stiva[i].first<<" "<<fixed<<setprecision(6)<<stiva[i].second<<'\n';
}