Cod sursa(job #697925)

Utilizator Ast09Stoica Anca Ast09 Data 29 februarie 2012 11:39:09
Problema Infasuratoare convexa Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include<fstream>
#include<cstdio>
#include<algorithm>
using namespace std;
ifstream f("infasuratoare.in");
FILE *g=fopen("infasuratoare.out","w");

struct punct{ double x,y;} p[120001];
int s[120001],r,k,infinit,v[120001],vf,n;
char nr[31];

void citire()
{ f>>n;
  for(int i=1;i<=n;i++) f>>p[i].x>>p[i].y;
  f.close();
}

void reper()
{ r=1;
  for(int i=2;i<=n;i++)
	  if(p[i].x<p[r].x||p[i].x==p[r].x&&p[i].y<p[r].y) r=i;
}

int mai_mic(int i,int j)
{ double a=(p[i].x-p[r].x)*(p[j].x-p[r].x);
  double b=(p[i].y-p[r].y)*(p[j].x-p[r].x)-(p[i].x-p[r].x)*(p[j].y-p[r].y);
  if(a<0&&b>0||a>0&&b<0) return 1;
  return 0;
}

void ordonare()
{ k=0;
  int i;
  for(i=1;i<=n;i++)
	  if(i!=r)
		  if(p[i].x==p[r].x)
			  if(!infinit||p[infinit].y<p[i].y) infinit=i;
				  else;
			  else { k++;
				     v[k]=i;
				   }
  /*int ord,m=k,aux;
  do{ ord=1;
	  for(i=1;i<m;i++)
		  if(mai_mic(v[i+1],v[i]))
			  { ord=0;
			    aux=v[i];
				v[i]=v[i+1];
				v[i+1]=aux;
			  }
	   m--;
    } while(!ord);*/

    sort(v+1,v+k+1,mai_mic);
}

int elim(int i)
{ double a=p[v[i]].x-p[s[vf]].x;
  double b=(p[s[vf-1]].y-p[v[i]].y)*a-(p[v[i]].y-p[s[vf]].y)*(p[s[vf-1]].x-p[v[i]].x);

  if(b<0&&a>0) return 1;
  return 0;
}

void stiva()
{ s[1]=r;
  s[2]=v[1];
  vf=2;
  for(int i=2;i<=k;i++)
	  {
	      while(elim(i)&&vf>2) vf--;
	      vf++;
		  s[vf]=v[i];
      }
}

void afis()
{ if(infinit) fprintf(g,"%d\n",vf+1);
    else fprintf(g,"%d\n",vf);
  for(int i=1;i<=vf;i++)  fprintf(g,"%.6lf %.6lf\n",p[s[i]].x,p[s[i]].y);
  if(infinit) fprintf(g,"%.6lf %.6lf\n",p[infinit].x,p[infinit].y);

}

int main()
{ citire(); reper(); ordonare(); stiva(); afis();

  fclose(g);
  return 0;
}