Pagini recente » Cod sursa (job #815890) | Cod sursa (job #2539987) | pascaliada | Cod sursa (job #3284490) | Cod sursa (job #2003238)
#include<fstream>
#include<iomanip>
#include<algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
pair <double,double> stiva[120003],a[120005];
int n;
bool parametru (const pair <double,double> &c, const pair <double,double> &d) {
if ((c.second-a[1].second)*(d.first-a[1].first)<(d.second-a[1].second)*(c.first-a[1].first)) return true;
return false;
}
double b[120005];
int main()
{
int 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];
sort(a+1,a+1+n,parametru);
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';
}