Pagini recente » Cod sursa (job #2845571) | Cod sursa (job #387755) | Cod sursa (job #3280281) | Cod sursa (job #892580) | Cod sursa (job #1328027)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,k,viz[1200001],s[120001];
float q;
struct puncte
{
float x,y;
}v[120001];
int sortare (puncte A, puncte B)
{
if(A.x!=B.x)
return A.x>B.x;
return A.y<B.y;
}
double determinant(puncte A,puncte B,puncte C)
{
//return (B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);
return A.x*B.y+B.x*C.y+C.x*A.y-C.x*B.y-B.x*A.y-A.x*C.y;
}
int main()
{
f>>n;
for(int i=1;i<=n;i++)
f>>v[i].x>>v[i].y;
sort(v+1,v+n+1,sortare);
for(int i=1;i<=2;i++)
{
s[i]=i;
}
k=2;viz[1]=0;viz[2]=1;
for(int i=3;i<=n;i++)
{
if(determinant(v[s[k]],v[s[k-1]],v[i])<0)
{
viz[i]=1;
s[++k]=i;
}
else
{
while(determinant(v[s[k]],v[s[k-1]],v[i])>=0 && k>1)
{
viz[s[k]]=0; s[k]=0; k--;
}
s[++k]=i;viz[i]=1;
}
}
for(int i=n-1;i>=1;i--)
{
if(viz[i]==0)
{
if(determinant(v[s[k]],v[s[k-1]],v[i])<0)
{
s[++k]=i;viz[i]=1;
}
else
{
while(determinant(v[s[k]],v[s[k-1]],v[i])>=0 && k>1)
{
viz[s[k]]=0; s[k]=0; k--;
}
s[++k]=i;viz[i]=1;
}
}
}
k--;
g<<k<<'\n';
for(int i=k;i>=1;i--)
{
g<<setprecision(6)<<fixed<<v[s[i]].x<<" ";
g<<setprecision(6)<<fixed<<v[s[i]].y<<'\n';
}
return 0;
}