Pagini recente » Cod sursa (job #1406983) | Cod sursa (job #2881060) | Cod sursa (job #119886) | Cod sursa (job #120093) | Cod sursa (job #545272)
Cod sursa(job #545272)
#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;
double x=Inf,y=Inf,aa,bb,cc;
struct Punct {double x,y;int viz;};
Punct P[NMax];
Punct St[NMax];
Punct PrimulPunct()//p0 e punctul cu y minim
{int k,i;
for(i=1;i<=n;i++)
if(x > P[i].x){k=i;y=P[i].y; x=P[i].x;}
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-1;i++)
if(!P[i].viz)
{
if(Verificare(St[m],P[i],P[i+1])>=0)
AddSt(P[i]);
P[i].viz=1;
}
}
int main()
{int i;
fscanf(f,"%d",&n);
for(i=1;i<=n;i++)
fscanf(f,"%lf%lf",&P[i].x,&P[i].y);
AddSt(PrimulPunct());
sort(P+1,P+n+1,criteria);//sortam in functie de y
Solve();
if(Verificare(St[m],P[n],P[1])>=0)
{AddSt(P[n]);P[n].viz=1;}
fprintf(g,"%d\n",m);
for(i=1;i<=m;i++)
fprintf(g,"%lf %lf\n",St[i].x,St[i].y);
return 0;
}