Cod sursa(job #403692)

Utilizator otilia_sOtilia Stretcu otilia_s Data 25 februarie 2010 10:36:47
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stdlib.h>
using namespace std;
const int NMAX=120002;
const double oo=1000000001;
double X[NMAX],Y[NMAX];
int n,ind[NMAX],psj,S[NMAX];

void citire()
{ FILE *fin=fopen("infasuratoare.in","r");
 fscanf(fin,"%d",&n);
 int i;
 psj=0; X[0]=oo; Y[0]=oo;
 for (i=1;i<=n;i++)
  {
   fscanf(fin,"%lf%lf",&X[i],&Y[i]);
   if (X[i]<X[psj] || (X[i]==X[psj] && Y[i]<Y[psj])) psj=i;
  }
 fclose(fin);
}

bool upolar(int i,int j)
{
    return (double)(X[i] - X[psj]) * (Y[j] - Y[psj]) > (double)(X[j] - X[psj]) * (Y[i] - Y[psj]);
}

double sens(int p1, int p2, int p3)
{
 return ((X[p2]-X[p1])*(Y[p3]-Y[p1])-(X[p3]-X[p1])*(Y[p2]-Y[p1]));
}

int main()
{
 citire();
 ind[0]=0;
 int i;
 for (i=1;i<=n;++i)
	if (i!=psj) ind[++ind[0]]=i;
 
 sort(ind+1,ind+1+ind[0],upolar);
 
 int ns=1;
 S[1]=psj;
 for (i=1;i<=ind[0];++i)
 {	
	while (ns>1 && sens(S[ns-1],S[ns],ind[i])<=0) --ns;
	S[++ns]=ind[i];
 }
  
  FILE *fout=fopen("infasuratoare.out","w");
  fprintf(fout,"%d\n",ns);
  for (i=1;i<=ns;++i)
   fprintf(fout,"%lf %lf\n",X[S[i]],Y[S[i]]);
  fclose(fout);
return 0;
}