Pagini recente » Cod sursa (job #181963) | Cod sursa (job #1447755) | Cod sursa (job #1734678) | Cod sursa (job #1475213) | Cod sursa (job #2535703)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <iomanip>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
vector< pair<double,double> > puncte;
vector< pair<double,double> > steve;
double determinant(pair<double,double> a, pair<double,double> b, pair<double,double> c)
{
return (a.first-c.first)*(b.second-c.second)-(a.second-c.second)*(b.first-c.first);
}
int n;
int main()
{
fin>>n;
for (int i=1;i<=n;i++)
{
double x,y;
fin>>x>>y;
puncte.push_back(make_pair(x, y));
}
sort(puncte.begin(), puncte.end());
/*for (int i=0;i<n;i++)
cout<<puncte[i].first<<' '<<puncte[i].second<<'\n';
cout<<'\n';*/
steve.push_back(puncte[0]);
steve.push_back(puncte[1]);
for (int i=2;i<n;i++)
{
steve.push_back(puncte[i]);
int j=steve.size()-1;
while (j>2&&determinant(steve[j], steve[j-1], steve[j-2])<0)
{
steve[j-1]=steve[j];
j--;
steve.pop_back();
}
}
for (int i=n-2;i>=0;i--)
{
steve.push_back(puncte[i]);
int j=steve.size()-1;
while (j>2&&determinant(steve[j], steve[j-1], steve[j-2])<0)
{
steve[j-1]=steve[j];
j--;
steve.pop_back();
}
}
steve.pop_back();
fout<<steve.size()<<'\n';
while (!steve.empty())
{
pair<double,double> yee=steve.back();
steve.pop_back();
fout<<setprecision(6)<<fixed<<yee.first<<' '<<yee.second<<'\n';
}
return 0;
}