Pagini recente » Cod sursa (job #58681) | Cod sursa (job #610352) | Cod sursa (job #2789755) | Cod sursa (job #982010) | Cod sursa (job #265835)
Cod sursa(job #265835)
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
double x[120001],y[120001];
long double V[120001];
int IND[120001],ST[120001],S;
bool cmp(int i,int j)
{
return (double)(x[i]-x[S])*(y[j]-y[S])<(double)(x[j]-x[S])*(y[i]-y[S]);
}
long double semn(int i1,int i2,int i3)
{
return (long double)x[i1] * y[i2] + x[i2] * y[i3] + x[i3] * y[i1] - y[i1] * x[i2] - y[i2] * x[i3] - y[i3] * x[i1];
}
int main()
{
FILE *in = fopen("infasuratoare.in","r");
FILE *out = fopen("infasuratoare.out","w");
int n,i;
fscanf(in,"%d",&n);
fscanf(in,"%lf %lf",&x[1],&y[1]);S=1;
for (i=2;i<=n;i++) {
fscanf(in,"%lf %lf",&x[i],&y[i]);
if (y[i]<y[S]) S = i;
else if (y[i]==y[S]) if (x[i]<x[S]) S = i;
}
for (i=1;i<=n;i++) if (i==S) continue;
else IND[++IND[0]] = i;
sort(IND+1,IND+IND[0]+1,cmp);
ST[0] = 1;
ST[ST[0]]=S;
for(int i = 1;i <= IND[0]; ++i)
{
if (IND[i] == S) continue;
while(ST[0] >= 2 && semn(ST[ST[0] - 1],ST[ST[0]],IND[i]) > 0) --ST[0];
ST[++ST[0]] = IND[i];
}
ST[++ST[0]] = S;
fprintf(out,"%d\n",ST[0] - 1);
reverse(ST + 1, ST + ST[0] + 1);
for(int i = 1;i < ST[0]; ++i)
{
fprintf(out,"%lf %lf\n",x[ST[i]],y[ST[i]]);
}
}