Pagini recente » Cod sursa (job #1177372) | Cod sursa (job #310664) | Cod sursa (job #3130931) | Cod sursa (job #1684913) | Cod sursa (job #2875005)
#include <fstream>
#include <stack>
#include <iomanip>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct puncte
{
double x,y;
bool operator <(puncte unu) const{
return (x<unu.x || (x==unu.x && y<unu.y));
}
}v[100002];
puncte pct;
int n;
puncte st[100002];
bool produs (puncte a, puncte b, puncte c)
{
if ((b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y)>=0)
return 1;
return 0;
}
int main()
{
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>v[i].x>>v[i].y;
}
sort (v+1,v+n+1);
int vf=1;
st[0]=v[1];
st[1]=v[2];
for (int i=3;i<=n;i++)
{
while (vf>0 && produs(st[vf-1],st[vf],v[i])>0)
{
vf--;
}
st[vf++]=v[i];
}
cout<<vf+1<<'\n';
while (vf>=0)
{
cout<<setprecision(9)<<fixed<<st[vf].x<<" "<<st[vf].y<<'\n';
vf--;
}
}