Pagini recente » Cod sursa (job #2886586) | Cod sursa (job #2113507) | Cod sursa (job #2251475) | Cod sursa (job #2797759) | Cod sursa (job #2159497)
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
#define x first
#define y second
typedef pair <double,double> point;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
point v[120001],d[120001];
int r,n;
double orientare(point a,point b,point c)
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int cmp(point p1, point p2)
{
return orientare(v[1],p1,p2)<0;
}
void sortare()
{
int q=1;
for(int i=2; i<=n; i++)
{
if(v[i]<v[q])
q=i;
}
swap(v[1],v[q]);
sort(v+2,v+n+1,cmp);
}
void convexhull()
{
sortare();
d[1]=v[1];
d[2]=v[2];
r=2;
for(int i=3; i<=n; i++)
{
while(r>=2 && orientare(d[r-1],d[r],v[i])>0)
r--;
d[++r]=v[i];
}
}
void afisare()
{
g<<fixed;
g<<r<<'\n';
for(int i=r; i>=1; i--)
{
g<<setprecision(9)<<d[i].x<<" "<<d[i].y<<'\n';
}
}
int main()
{
f>>n;
for(int i=1; i<=n; i++)
{
f>>v[i].x>>v[i].y;
}
convexhull();
afisare();
return 0;
}