Cod sursa(job #411593)

Utilizator adrianraduleaRadulea Adrian adrianradulea Data 4 martie 2010 23:38:37
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include<stdio.h>
#include<algo.h>
using namespace std; 
FILE *f,*g;
long n,i,a[120100],k,st[120100],ok,ct,cauta; float x[120100],y[120100],negasit,viz[120100];
int cmp(int a,int b)
{ return x[a]<x[b]||x[a]==x[b]&&y[a]<y[b]; }
float det(long v1,long v2,long v3)
{ return x[a[v1]]*y[a[v2]]+x[a[v2]]*y[a[v3]]-x[a[v3]]*y[a[v2]]-x[a[v2]]*y[a[v1]]-y[a[v3]]*x[a[v1]]+y[a[v1]]*x[a[v3]]; }
int main()
{ f=fopen("infasuratoare.in","r"); g=fopen("infasuratoare.out","w");
  fscanf(f,"%ld",&n); for(i=1;i<=n;i++) fscanf(f,"%f%f",&x[i],&y[i]);
  for(i=1;i<=n;i++) a[i]=i;
  sort(a+1,a+n+1,cmp);
  k=2; st[1]=1; st[2]=2; ok=1; ct=3;
  while(ok)
   { cauta=1; ct=st[k]+1;
     while(cauta) 
		if(det(ct,st[k],st[k-1])>=0) { k++; st[k]=ct; cauta=0; } 
		else k--;
     if(st[k]==n) ok=0;
   }
 for(i=1;i<=k;i++) viz[st[i]]=1; ok=1; viz[st[1]]=0; 
 while(ok)
   { cauta=1; negasit=1; for(i=n;i>=1&&negasit;i--) if(viz[i]==0) { negasit=0; ct=i; } 
     while(cauta) 
		if(det(ct,st[k],st[k-1])>=0) { k++; st[k]=ct; viz[st[k]]=1; cauta=0; } 
		else k--;
     if(st[k]==st[1]) ok=0;
   }
 for(i=1;i<k;i++) fprintf(g,"%f %f\nv",x[a[st[i]]],y[a[st[i]]]);
 fclose(g);
 return 0;
}