Pagini recente » Cod sursa (job #1018056) | Cod sursa (job #232207) | Cod sursa (job #2029004) | Cod sursa (job #1630946) | Cod sursa (job #2119239)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point
{
double x;
double y;
};
double cross(point o,point a,point b)
{
return (a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y);
}
bool wayToSort(point lh,point rh)
{
if(lh.x==rh.x) return lh.y<rh.y;
else return lh.x<rh.x;
}
vector <point> p;
vector <point> l;
vector <point> u;
vector <point> raspuns;
int nr;
int main()
{
point foo;
fin>>nr;
for(int i=0;i<nr;i++)
{
fin>>foo.x>>foo.y;
p.push_back(foo);
}
sort(p.begin(),p.end(),wayToSort);
fout<<setprecision(12);
for(int i=0;i<nr;i++)
{
while(u.size()>=2&&cross(u.back(),u[u.size()-2],p[i])<=0)
u.pop_back();
u.push_back(p[i]);
}
for(int i=nr-1;i>=0;i--)
{
while(l.size()>=2&&cross(l.back(),l[l.size()-2],p[i])<=0)
l.pop_back();
l.push_back(p[i]);
}
u.pop_back();
l.pop_back();
raspuns=u;
raspuns.insert(raspuns.end(),l.begin(),l.end());
//sort(raspuns.begin(),raspuns.end(),wayToSort);
fout<<raspuns.size()<<"\n";
for(int i=raspuns.size()-1;i>=0;i--)
{
fout<<raspuns[i].x<<" "<<raspuns[i].y<<"\n";
}
return 0;
}