Pagini recente » Cod sursa (job #1555529) | Cod sursa (job #2226727) | Cod sursa (job #3140031) | Cod sursa (job #2237683) | Cod sursa (job #2220059)
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
int n,afis[120002],t,i;
struct vct
{
double x,y;
}v[120002];
bool cmp (vct A , vct B)
{
if (A.y==B.y)
return A.x<B.x;
else
return A.y<B.y;
}
int determinant(int x, int y, int z)
{
double delta,a1,a2,a3,b1,b2,b3;
a1=v[x].x; b1=v[x].y;
a2=v[y].x; b2=v[y].y;
a3=v[z].x; b3=v[z].y;
delta=a1*b2+a2*b3+a3*b1-a3*b2-a1*b3-a2*b1;
if(delta>=0)
return 1;
else
return 0;
}
int main()
{
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
f>>n;
for(i=1;i<=n;i++)
f>>v[i].x>>v[i].y;
sort(v+1,v+1+n,cmp);
afis[1]=1;
afis[2]=2;
t=2;
for(i=3;i<=n;i++)
{
if(!determinant(afis[t],afis[t-1],i))
afis[++t]=i;
else
{
while(determinant(afis[t],afis[t-1],i))
t--;
afis[++t]=i;
}
}
afis[++t]=n-1;
for(i=n-2;i>=1;i--)
{
if(!determinant(afis[t],afis[t-1],i))
afis[++t]=i;
else
{
while(determinant(afis[t],afis[t-1],i))
t--;
afis[++t]=i;
}
}
g<<t-1<<'\n';
for(i=1;i<t;i++)
g<<fixed<<setprecision(6)<<v[afis[i]].x<<' '<<fixed<<setprecision(6)<<v[afis[i]].y<<'\n';
return 0;
}