Pagini recente » Cod sursa (job #1347715) | Cod sursa (job #714326) | Cod sursa (job #1889525) | Cod sursa (job #2176686) | Cod sursa (job #407605)
Cod sursa(job #407605)
#include <cstdio>
#include <cstring>
#include <vector>
#include<algorithm>
using namespace std;
#define fi first
#define se second
pair<double,double > a[120050];
int q[120050],v[120050];
const double eps=0.000000000001;
FILE *in,*out;
int parte(int i,int j,int k)
{
double A=a[i].se-a[j].se;
double B=a[j].fi-a[i].fi;
double C=a[i].fi*a[j].se-a[i].se*a[j].fi;
double rez=A*a[k].fi+B*a[k].se+C;
if (-eps<=rez&&rez<=eps)
return 0;
if (rez<0)
return -1;
return 1;
}
int main()
{
int i,n,pas,u;
in=fopen("infasuratoare.in","r");
out=fopen("infasuratoare.out","w");
fscanf(in,"%d",&n);
for(i=1;i<=n;i++)
{
fscanf(in,"%lf %lf",&a[i].fi,&a[i].se);
}
sort(a+1,a+n+1);
pas=1;
q[u=1]=1;
v[1]=1;
for (i=1;i>=1;i+=pas)
{
if (i==n)
{
pas=-1;
v[1]=0;
}
if (v[i])
continue;
while (u>1&&parte(q[u-1],i,q[u])==1)
{
v[q[u]]=0;
u--;
}
u++;
q[u]=i;
v[i]=1;
}
fprintf(out,"%d\n",u-1);
for(i=1;i<u;i++)
fprintf(out,"%lf %lf\n",a[q[i]].fi,a[q[i]].se);
fclose(in);
fclose(out);
return 0;
}