Pagini recente » Cod sursa (job #2885050) | Cod sursa (job #920186) | Cod sursa (job #1240675) | Cod sursa (job #2558882) | Cod sursa (job #3039927)
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
int n,poz;
long double xmin,ymin;
struct punct
{
long double x,y;
};
punct v[120005];
punct q[120005];
punct p0;
long double dist (punct a,punct b)
{
long double rasp = (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
return rasp;
}
long double orientare (punct a,punct b,punct c)
{
long double v = (b.y-a.y)*(c.x-a.x) - (c.y-a.y)*(b.x-a.x);
if (v==0)
return 0;
if (v>0)
return 1;
if (v<0)
return 2;
}
bool fcmp (punct a,punct b)
{
int o = orientare(p0,a,b);
if (o==0)
{
if (dist(p0,a) >= dist(p0,b))
return false;
return true;
}
else
{
if (o==2)
return true;
return false;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int i,j;
cin >> n;
xmin = 2e9;
ymin = 2e9;
for(i=1;i<=n;i++)
{
cin >> v[i].x >> v[i].y;
if (v[i].y < ymin)
{
ymin = v[i].y;
xmin = v[i].x;
poz = i;
}
else if (v[i].y == ymin && v[i].x<xmin)
{
xmin = v[i].x;
poz = i;
}
}
swap(v[1],v[poz]);
p0 = v[1];
sort(v+2,v+n+1,fcmp);
int vf = 2;
q[1] = v[1];
q[2] = v[2];
for (i=3;i<=n;i++)
{
while (vf > 1 && orientare(q[vf-1],q[vf],v[i])!=2)
vf--;
q[++vf] = v[i];
}
cout << vf << '\n';
for(i=1;i<=vf;i++)
cout << fixed << setprecision(15) << q[i].x << ' ' << q[i].y << '\n';
return 0;
}