Pagini recente » Profil Matoka26 | Cod sursa (job #1444448) | Cod sursa (job #2158751) | Cod sursa (job #1050008) | Cod sursa (job #1589879)
#include <fstream>
#include <iomanip>
#include <algorithm>
#define lmax 120005
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct el
{
long double x,y;
}
v[lmax],s[lmax];
double unghi(el a,el b,el c)
{
return a.x*b.y+a.y*c.x+b.x*c.y-b.y*c.x-a.y*b.x-a.x*c.y;
}
int comp(el e1,el e2)
{
return unghi(v[1],e1,e2)>0;
}
int n,nr,i,a,b,c;
int main()
{
f>>n>>v[1].x>>v[1].y;
for (i=2;i<=n;i++)
{
f>>v[i].x>>v[i].y;
if (v[i].x!=v[1].x)
{
if (v[i].x<v[1].x)
swap(v[1],v[i]);
}
else
if (v[i].y<v[1].y)
swap(v[1],v[i]);
}
sort(v+2,v+n+1,comp);
s[1]=v[1];
s[2]=v[2];
nr=2;
for (i=3;i<=n;i++)
{
while (unghi(s[nr-1],s[nr],v[i])<=0 && nr>=2)
nr--;
nr++;
s[nr]=v[i];
}
g<<nr<<'\n';
for (i=1;i<=nr;i++)
g<<fixed<<setprecision(6)<<s[i].x<<" "<<s[i].y<<'\n';
f.close();
g.close();
}