Cod sursa(job #301283)

Utilizator diannaDiaconu Diana dianna Data 8 aprilie 2009 08:39:47
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include<fstream.h>
#include<stdio.h>
FILE *f,*g;
const int Nmax=121000;
int lh,*st,*st2,vf,vf2;
long n,nr;
struct punct
{
	float x,y;
}*h;

void urca(int k)
{
 while(h[k].x<h[k/2].x)
 {
	punct z=h[k];
	h[k]=h[k/2];
	h[k/2]=z;
	k=k/2;
 }
}

void coboara(int k)
{
 int fiu;
 while(k<n)
 {
	fiu=k;
	if(h[fiu].x>h[k*2].x && k*2<=lh)
		fiu=2*k;
	if(h[fiu].x>h[k*2+1].x && k*2+1<=lh)
		fiu=2*k+1;
	if(fiu!=k)
	{
	       punct z=h[fiu];
	       h[fiu]=h[k];
	       h[k]=z;
	       k=fiu;
	}
	else
		break;
 }
}

void citire()
{
 f=fopen("infasura.in","r");
 g=fopen("infasura.out","w");
 float a,b;
 int i;
 fscanf(f,"%d",&n);
 for(i=0;i<n;i++)
 {
	fscanf(f,"%f%f",&a,&b);
	h[++lh].x=a;
	h[lh].y=b;
	urca(lh);
 }
 for(i=1;i<=n;i++)
 {
	punct z=h[1];
	h[1]=h[lh];
	h[lh]=z;
	lh--;
	coboara(1);
 }
}

void afisare()
{
 for(int i=1;i<=vf;i++)
	fprintf(g,"%.6f %.6f\n",h[st[i]].x,h[st[i]].y);
}

void traseu_jos()
{
 int k=3;
 st[1]=1;
 st[2]=2;
 vf=2;
 while(k<=n)
 {
	while(h[k].y<h[st[vf]].y && h[st[vf-1]].y<h[st[vf]].y)
		vf--;
	st[++vf]=k++;
 }
 nr=vf;
 //afisare();
}

void traseu_sus()
{
 int k=3;
 st2[1]=1;
 st2[2]=2;
 vf2=2;
 while(k<=n)
 {
	while(h[k].y>h[st2[vf2]].y && h[st2[vf2-1]].y>h[st2[vf2]].y)
		vf2--;
	st2[++vf2]=k++;
 }
}

int main()
{
 st=new int[Nmax];
 st2=new int[Nmax];
 h=new punct[Nmax];
 citire();
 traseu_jos();
 traseu_sus();
 fprintf(g,"%d\n",vf+vf2-2);
 afisare();
 for(int i=vf-1;i>0;i--)
	fprintf(g,"%.6f %.6f\n",h[st2[i]].x,h[st2[i]].y);
 fclose(f);
 fclose(g);
 return 0;
}