Cod sursa(job #697666)

Utilizator andrei.finaruFinaru Andrei Emanuel andrei.finaru Data 29 februarie 2012 10:27:39
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.39 kb
#include <fstream>
#include <cstdio>
#include <algorithm>

using namespace std;

ifstream f("infasuratoare.in");
//ofstream g("infasuratoare.out");
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;
    sort(v+1,v+k+1,mai_mic);
    //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);*/
}

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);
    //g<<"elim "<<a<<' '<<b<<'\n';
    if(b<=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];
		//for(int j=vf;j>0;j--) g<<s[j]<<' ';
		//g<<'\n';
    }
}

void afis()
{
    if(infinit)  fprintf(g,"%d\n",vf+1);
        else fprintf(g,"%d\n",vf);
	//g<<vf+1<<'\n';
	//else g<<vf<<'\n';
    for(int i=1;i<=vf;i++)
	  //g<<p[s[i]].x<<' '<<p[s[i]].y<<'\n';
    {
        fprintf(g,"%.6lf %.6lf\n",p[s[i]].x,p[s[i]].y);
        /*fprintf(g,"%.6lf",p[s[i]].x);
        fprintf(g,"%c",' ');
        fprintf(g,"%.6lf",p[s[i]].y);
        fprintf(g,"%c",'\n');*/
    }
	  /*{ double aux=p[s[i]].x;
	    int z=10;
	    while(p[s[i]].x/z) z*=10;
		z/=10;
		nr[0]=p[s[i]].x/z;*/
    if(infinit)fprintf(g,"%.6lf %.6lf\n",p[infinit].x,p[infinit].y);
    //g<<p[infinit].x<<' '<<p[infinit].y<<'\n';
    //g.close();
}

int main()
{
    citire(); reper(); ordonare(); stiva(); afis();
    //for(int i=1;i<=k;i++) g<<v[i]<<' ';
    //g.close();
    fclose(g);
    return 0;
}