Pagini recente » Cod sursa (job #373455) | Cod sursa (job #1418886) | Cod sursa (job #2376716) | Cod sursa (job #854811) | Cod sursa (job #2527130)
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <fstream>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
double x,y;
vector <pair <double,double> > v;
vector <pair <double,double> > s;
double prod(pair <double,double> A,pair <double,double> B,pair <double,double> C)
{
return (B.first-A.first)*(C.second-A.second)-(B.second-A.second)*(C.first-A.first);
}
int comp(pair <double,double> A,pair <double,double> B)
{
return prod(v[0],A,B)<0;
}
void sortare()
{
int poz=0;
for(int i=1;i<v.size();i++)
if(v[poz]>v[i])
poz=i;
swap(v[0],v[poz]);
sort(v.begin()+1,v.end(),comp);
}
void rezconv()
{
sortare();
//fout<<v[0].first<<" "<<v[0].second<<endl;
s.push_back(v[0]);
s.push_back(v[1]);
for(int i=2;i<v.size();i++)
{
while(s.size()>=1 && prod(s[s.size()-2],s[s.size()-1],v[i])>0)
s.pop_back();
s.push_back(v[i]);
}
}
int main()
{
fin>>n;
for(int i=1;i<=n;i++)
{
fin>>x>>y;
v.push_back(make_pair(x,y));
}
rezconv();
fout<<s.size()<<'\n';
fout<<fixed;
for(int i=s.size()-1;i>=0;i--)
fout<<setprecision(9)<<s[i].first<<" "<<s[i].second<<'\n';
return 0;
}