Pagini recente » Cod sursa (job #1619352) | Cod sursa (job #2631139) | Cod sursa (job #718939) | Cod sursa (job #2894982) | Cod sursa (job #264728)
Cod sursa(job #264728)
#include<stdio.h>
using namespace std;
float t[120010];
struct punct {long double 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||t[i]==t[j]&&v[i].x==v[j].x&&v[i].y<v[j].y)
{ 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()
{
FILE *f=fopen("infasuratoare.in","r");
fscanf(f,"%d",&n);
p.x=1000000000; p.y=1000000000;
for(i=0;i<n;i++)
{
fscanf(f,"%Lf %Lf",&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];}
}
fclose(f);
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);
if(v[s[k]].y==v[s[k-1]].y&&v[s[k]].y==v[i].y||v[s[k]].x==v[s[k-1]].x&&v[s[k]].x==v[i].x) s[k]=i;
else s[++k]=i;
}
}
FILE *g=fopen("infasuratoare.out","w");
fprintf(g,"%d\n",k);
for(i=1;i<=k;i++)
fprintf(g,"%0.6Lf %0.6Lf\n",v[s[i]].x,v[s[i]].y);
fclose(g);
return 0;
}