Pagini recente » Cod sursa (job #2673911) | Cod sursa (job #619211) | Cod sursa (job #2192872) | Cod sursa (job #2257737) | Cod sursa (job #2978012)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define double long double
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
vector< pair <double, double>> v, hull;
vector< pair< double, double>> convex_hull(vector< pair< double, double>>);
int convex(pair<double, double>, pair<double, double>, pair<double, double>);
int main()
{
int i, n;
double a, b;
fin>>n;
for(i=1; i<=n; i++)
{
fin>>a>>b;
v.push_back(make_pair(a, b));
}
hull=convex_hull(v);
fout<<hull.size()<<'\n';
for(auto i:hull) fout<<fixed<<setprecision(12)<<i.first<<' '<<i.second<<'\n';
}
int convex(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);
}
vector< pair< double, double>> convex_hull(vector< pair< double, double>> v)
{
pair< double, double> p1, p2;
vector< pair< double, double>> hull;
hull.clear();
sort(v.begin(), v.end());
for(auto i:v)
{
while(hull.size()>=2)
{
p1=hull[hull.size()-2];
p2=hull[hull.size()-1];
if(convex(p2, i, p1)<=0) break;
hull.pop_back();
}
hull.push_back(i);
}
hull.pop_back();
reverse(v.begin(), v.end());
for(auto i:v)
{
while(hull.size()>=2)
{
p1=hull[hull.size()-2];
p2=hull[hull.size()-1];
if(convex(p2, i, p1)<=0) break;
hull.pop_back();
}
hull.push_back(i);
}
hull.pop_back();
return hull;
}