Cod sursa(job #265835)

Utilizator free2infiltrateNezbeda Harald free2infiltrate Data 24 februarie 2009 16:12:48
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#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]]);
}
}