Pagini recente » Cod sursa (job #1265650) | Cod sursa (job #2247300) | Cod sursa (job #2777048) | Cod sursa (job #1366102) | Cod sursa (job #3205157)
#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;
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
{
if(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.pop_back();
s.push_back({v[i].first,v[i].second});
}
}
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;
}