Pagini recente » Cod sursa (job #283811) | Cod sursa (job #3275813) | Cod sursa (job #2925666) | Cod sursa (job #1895194) | Cod sursa (job #3159125)
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n,k=2;
struct point{
double x,y;
}v[120000],sol[120000];
enum orientare
{
trigonometric,
orar,
coliniar,
};
void citire()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>v[i].x>>v[i].y;
}
}
void afisare()
{
cout<<k<<'\n';
for(int i=0;i<k;i++)
cout<<fixed<<setprecision(6)<<sol[i].x<<' '<<sol[i].y<<'\n';
}
bool cmp(point a,point b)
{
if(a.x!=b.x)
return a.x<b.x;
return a.y<b.y;
}
double det(point p1,point p2,point p3)
{
return (p1.y-p2.y)*(p3.x-p2.x)-(p3.y-p2.y)*(p1.x-p2.x);
}
orientare calcul(point a,point b,point c)
{
double d=det(a,b,c);
if(d>0)
return trigonometric;
if(d==0)
return coliniar;
return orar;
}
void bkt()
{
for(int x=2;x<n;x++)
{
while(calcul(sol[k-2],sol[k-1],v[x])==trigonometric)
{
k--;
}
sol[k++]=v[x];
}
}
void bkt2()
{
for(int x=n-2;x>=2;x--)
{
while(calcul(sol[k-2],sol[k-1],v[x])==trigonometric)
{
k--;
}
sol[k++]=v[x];
}
}
int main()
{
citire();
sort(v,v+n,cmp);
sol[0]=v[0];
sol[1]=v[1];
bkt();
bkt2();
if(calcul(sol[k-2],sol[k-1],sol[0])==trigonometric)
k--;
afisare();
return 0;
}