Pagini recente » Cod sursa (job #2783758) | Cod sursa (job #2264840) | Cod sursa (job #333556) | Cod sursa (job #740080) | Cod sursa (job #545568)
Cod sursa(job #545568)
#include<cstdio>
#include<algorithm>
#define NMax 120000
#define Inf 1300000000
using namespace std;
FILE *f=fopen("infasuratoare.in","r");
FILE *g=fopen("infasuratoare.out","w");
int n,m;
struct Punct {double x,y;int viz;};
Punct P[NMax];
Punct St[NMax];
Punct PrimulPunct()//p0 e punctul cu y minim
{int k,i;
double x=Inf,y=Inf;
for(i=1;i<=n;i++)
if(x > P[i].x){k=i;x=P[i].x; y=P[i].y;}
else
if(x==P[i].x && y > P[i].y){k=i;x=P[i].x;y=P[i].y;}
P[k].viz=1;
return P[k];
}
void AddSt(Punct O)
{St[++m]=O;
}
bool criteria(Punct i,Punct j)
{return (j.x-St[1].x)*(i.y-St[1].y) < (i.x-St[1].x)*(j.y-St[1].y);
}
double Verificare(Punct A,Punct B,Punct C)
{return (long double)(B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);
}
void Solve()
{int i;
for(i=1;i<=n;i++)
{
while(m>=2 && Verificare(St[m-1],St[m],P[i])<0)
m--;
AddSt(P[i]);
}
}
int main()
{int i,j;
Punct Q;
fscanf(f,"%d",&n);
for(i=1;i<=n;i++)
fscanf(f,"%lf%lf",&P[i].x,&P[i].y);
AddSt(PrimulPunct());
for(i=1;i<=n;i++)
if(P[i].viz==1)
{
Q=P[i];
for(j=i+1;j<=n;j++)
P[j-1]=P[j];
n--;
break;
}
sort(P+1,P+n+1,criteria);//sortam in functie de tangenta
P[n+1]=Q;
Solve();
fprintf(g,"%d\n",m);
for(i=1;i<=m;i++)
fprintf(g,"%lf %lf\n",St[i].x,St[i].y);
return 0;
}