Pagini recente » Cod sursa (job #2389379) | Cod sursa (job #2392637) | Cod sursa (job #400085) | Cod sursa (job #1155715) | Cod sursa (job #2978015)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define double long double
#define int long long
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
vector< pair <double, double>> v, hull1, hull2;
vector< pair< double, double>> convex_hull(vector< pair< double, double>>);
int convex(pair<double, double>, pair<double, double>, pair<double, double>);
signed 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));
}
hull1=convex_hull(v);
reverse(v.begin(), v.end());
hull2=convex_hull(v);
fout<<hull1.size()+hull2.size()<<'\n';
for(auto i:hull1) fout<<fixed<<setprecision(12)<<i.first<<' '<<i.second<<'\n';
for(auto i:hull2) fout<<fixed<<setprecision(12)<<i.first<<' '<<i.second<<'\n';
}
int convex(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);
}
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(p1, p2, i)<=0) break;
hull.pop_back();
}
hull.push_back(i);
}
hull.pop_back();
return hull;
}