Pagini recente » Cod sursa (job #1478474) | Cod sursa (job #2173819) | Cod sursa (job #2719279) | Cod sursa (job #2950651) | Cod sursa (job #3205162)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
double minx=1000000,miny=1000000;
vector <pair<double,double>> v;
vector <pair<double,double>> s;
int det(double x1,double y1,double x2,double y2,double x3,double y3);
bool sortare(pair<double,double> x,pair<double,double> y)
{
if(x.first==minx && x.second==miny)
return 1;
if(y.first==minx && y.second==miny)
return 0;
if(det(minx,miny,x.first,x.second,y.first,y.second)==-1)
return 1;
return 0;
}
int main()
{
fin>>n;
for(int i=1;i<=n;i++)
{
double x,y;
fin>>x>>y;
if(minx>x)
{
minx=x;
miny=y;
}
v.push_back({x,y});
}
sort(v.begin(),v.end(),sortare);
s.push_back({minx,miny});
for(int i=1;i<v.size();i++)
{
if(s.size()==1)
s.push_back({v[i].first,v[i].second});
else
{
while(det(s[s.size()-2].first,s[s.size()-2].second,s[s.size()-1].first,s[s.size()-1].second,v[i].first,v[i].second)==1 && s.size()>=2)
s.pop_back();
s.push_back({v[i].first,v[i].second});
}
}
while(det(s[s.size()-2].first,s[s.size()-2].second,s[s.size()-1].first,s[s.size()-1].second,s[0].first,s[0].second)==1 && s.size()>2)
s.pop_back();
fout<<s.size()<<'\n';
for(int i=s.size()-1;i>=0;i--)
{
fout<<setprecision(5)<<fixed;
fout<<s[i].first<<' '<<s[i].second<<'\n';
}
return 0;
}
int det(double x1,double y1,double x2,double y2,double x3,double y3)
{
double aux=(x1*y2+x2*y3+y1*x3)-(x3*y2+y3*x1+x2*y1);
if(aux<0)
return -1;
return 1;
}