Pagini recente » Cod sursa (job #1304053) | Cod sursa (job #1374112) | Cod sursa (job #146118) | Cod sursa (job #111186) | Cod sursa (job #2573083)
#include <bits/stdc++.h>
#define ld long double
#define Nmax 120005
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
ld x, y;
};
punct p[Nmax];
int n, nr, s[Nmax], r;
ld produs(punct A, punct B, punct C)
{
return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
ld distanta(punct A, punct B)
{
return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);
}
bool criteriu(punct A, punct B)
{
if(produs(p[1], A, B)==0)
return distanta(p[1], A)<distanta(p[1], B);
return produs(p[1], A, B)>0;
}
int gaseste()
{
ld minx=p[1].x, miny=p[1].y;
int r;
for(int i=2;i<=n;i++)
{
if(minx>p[i].x)
{
minx=p[i].x;
miny=p[i].y;
r=i;
}
else if(minx==p[i].x && miny>p[i].y)
{
miny=p[i].y;
r=i;
}
}
return r;
}
int main()
{
fin >> n;
fin >> p[1].x >> p[1].y;
for(int i=2;i<=n;i++)
fin >> p[i].x >> p[i].y;
r=gaseste();
swap(p[1], p[r]);
sort(p+2, p+n+1, criteriu);
nr=1;
s[1]=1;
for(int i=2;i<=n;i++)
{
while(nr>1 && produs(p[s[nr-1]], p[s[nr]], p[i])<0)
nr--;
nr++;
s[nr]=i;
}
fout << nr << '\n';
for(int i=1;i<=nr;i++)
fout << setprecision(12) << fixed << p[s[i]].x << ' ' << p[s[i]].y << '\n';
return 0;
}