Pagini recente » Cod sursa (job #1264136) | Cod sursa (job #2350098) | Cod sursa (job #749170) | Cod sursa (job #1684105) | Cod sursa (job #2280191)
#include <fstream>
#include<iomanip>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
struct punct
{
double x,y;
}p[120005],primul,s[120005];
inline double cp(punct A, punct B, punct C) {
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
int criteriu(punct p1, punct p2) {
return cp(p[1], p1, p2) < 0;
}
int main()
{
int vf,poz;
fin>>n;
fin>>p[1].x>>p[1].y;
poz=1;
for(int i=2;i<=n;i++)
{
fin>>p[i].x>>p[i].y;
if(p[i].x<p[poz].x)
{
poz=i;
}
else
{
if(p[i].x==p[poz].x && p[i].y<p[poz].y)
{
poz=i;
}
}
}
swap(p[1], p[poz]);
sort(p + 2, p + n + 1, criteriu);
s[1]=p[1];
s[2]=p[2];
vf=2;
for(int i=3;i<=n;i++)
{
while(vf>=2 && cp(s[vf-1],s[vf],p[i])>0)
{
--vf;
}
s[++vf]=p[i];
}
fout << fixed;
fout<<vf<<'\n';
for (int i = vf; i >= 1; --i)
fout << setprecision(5) << s[i].x << " " << s[i].y << "\n";
return 0;
}