Pagini recente » Cod sursa (job #2046811) | Cod sursa (job #2864119) | Cod sursa (job #950119) | Cod sursa (job #1843237) | Cod sursa (job #264681)
Cod sursa(job #264681)
#include<fstream>
using namespace std;
float t[120010];
struct punct {float x,y;} v[120010],p,aux;
int i,j,n,k,poz,s[120010];
int pozitie(int i, int j)
{ int di=1,dj=0,aux2;
float aux3;
while(i<j)
{ if(t[i]>t[j]||t[i]==t[j]&&v[i].x>v[j].x)
{ aux3=t[i]; t[i]=t[j]; t[j]=aux3;
aux2=di; di=dj; dj=aux2;
aux=v[i]; v[i]=v[j]; v[j]=aux;
}
i+=di;
j-=dj;
}
return i;
}
void quick(int s, int d)
{ if(s<d)
{ int p=pozitie(s,d);
quick(s,p-1);
quick(p+1,d);
}
}
void elimin(int &k)
{ long double S;
int a=s[k-1],b=s[k];
S= v[a].x*v[b].y-
v[i].x*v[b].y+
v[b].x*v[i].y-
v[b].x*v[a].y+
v[i].x*v[a].y-
v[a].x*v[i].y;
if(S<0) elimin(--k);
}
int main()
{
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
f>>n; p.x=1000000000; p.y=1000000000;
for(i=0;i<n;i++)
{
f>>v[i].x>>v[i].y;
if(v[i].x<p.x||v[i].x==p.x&&v[i].y<p.y) {poz=i; p=v[i];}
}
aux=v[0]; v[0]=v[poz]; v[poz]=aux;
for(i=1;i<n;i++)
t[i]=(float)(v[i].y-p.y)/(v[i].x-p.x);
quick(1,n-1);
s[1]=0; s[2]=1; k=2;
for(i=2;i<n;i++)
{ if(t[i]!=t[i+1])
{ elimin(k);
s[++k]=i;
}
}
g<<k<<'\n';
for(i=1;i<=k;i++)
g<<v[s[i]].x<<" "<<v[s[i]].y<<'\n';
f.close();
g.close();
return 0;
}