Cod sursa(job #253438)

Utilizator Sorin_IonutBYSorynyos Sorin_Ionut Data 5 februarie 2009 19:51:07
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAX 120000
#define INF 1000000000
#define IN "infasuratoare.in"
#define OUT "infasuratoare.out"

FILE *fin=fopen(IN,"r");
FILE *fout=fopen(OUT,"w");

double X[MAX],Y[MAX];
long double V[MAX];
int IND[MAX],ST[MAX];
int PI,N;

long double semn(int,int,int);
void swap(int,int);
bool cmpf(int,int);

int main()
{
 int i;
    
 fscanf(fin,"%d\n",&N);
   
 X[0]=INF;
 Y[0]=INF;
  
 int punct_initial=0;
  
 for(i=1;i<=N;++i)
 {
  fscanf(fin,"%lf %lf",&X[i],&Y[i]);
   
  if(X[i]<X[punct_initial] || (X[i]==X[punct_initial] && Y[i]<Y[punct_initial]))
   punct_initial=i;
 }
 
 fclose(fin);
  
 PI=punct_initial;
  
 for(i=1;i<=N;++i)
 {
  if(i==punct_initial)
   continue; 
  IND[++IND[0]]=i;
 }

 sort(IND+1,IND+IND[0]+1,cmpf);
  
 ST[ST[0]=1]=punct_initial;
 
 for(i=1;i<=IND[0];++i)
 {
  if(IND[i]==punct_initial)
   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]]=punct_initial;
  
 fprintf(fout,"%d\n",ST[0]-1);
  
 swap(ST[1],ST[ST[0]+1]);
  
 for(i=ST[0]-1;i>0;i--)
  fprintf(fout,"%lf %lf\n",X[ST[i]],Y[ST[i]]);
 fclose(fout);
 
 return 0;
}

long double semn(int i,int j,int k)
{
 return (long double) (X[i]*Y[j]+X[j]*Y[k]+X[k]*Y[i])-(Y[i]*X[j]+Y[j]*X[k]+Y[k]*X[i]);
}

bool cmpf(int i,int j)
{
 return (double)(X[i]-X[PI])*(Y[j]-Y[PI])<(double)(X[j]-X[PI])*(Y[i]-Y[PI]);
}

void swap(int i,int j)
{
 int k;
 k=i; i=j; j=k;
}