Cod sursa(job #1011460)

Utilizator radu2004GOLD radu radu2004 Data 16 octombrie 2013 21:06:44
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.94 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
struct punct {double x;double y;};
punct a[120003];
int st[120003],use[120003],prim,ultim,n;
float x1,x2;
FILE *f,*g;
int verif (punct c,punct a,punct b)
{
    double y1;
    if (a.y==b.y) return c.y<a.y;
    else
    {y1=((c.y-a.y)*(a.x-b.x))/(a.y-b.y) +a.x;
    return y1>=c.x;}
}
void schimb (punct &v,punct &v1)
{
    int aux;
    aux=v.y;
    v.y=v1.y;
    v1.y=aux;
     aux=v.x;
    v.x=v1.x;
    v1.x=aux;
}
/*void sort (int s,int d)
{
    int m;
    if (s<d)
    {
        int i=s,j=d,pi=0,pj=1;
        while (i<j)
        {
            if (a[i].y>a[j].y) {schimb (a[i],a[j]);int aux=pi;pi=pj;pj=aux;}
              else if (a[i].y==a[j].y && a[i].x<a[j].x) {schimb (a[i],a[j]);int aux=pi;pi=pj;pj=aux;}
        i+=pi;
        j-=pj;
        }
        m=i;
        sort (s,m-1);
        sort (m+1,d);

    }
}*/


int main()
{f=fopen ("infasuratoare.in","r");
 g=fopen ("infasuratoare.out","w");
 fscanf (f,"%d",&n);
int i;
 for ( i=1;i<=n;i++)
            fscanf (f,"%lf%lf",&a[i].x,&a[i].y);
 //sort (1,n);
 st[1]=1;
 st[2]=2;
 prim=2;
 ultim=2;use[2]=1;
 for (i=3;i<=n;i++)
  {  if (verif (a[i],a[st[prim-1]],a[st[prim]])) {st[++prim]=i;use[i]=1;}
       else
        {
            while (!verif (a[i],a[st[prim-1]],a[st[prim]]) && prim>=2) {use[st[prim]]=0;
                                                                        prim--;}
            st[++prim]=i;
            use[i]=1;
        }

  }
  ultim=prim-1;
  st[++prim]=n-1;
  for (i=n-2;i>=1;i--)
  {  if (!verif (a[i],a[st[prim-1]],a[st[prim]]) && use[i]==0) st[++prim]=i;
       else
        {
            while (verif (a[i],a[st[prim-1]],a[st[prim]]) && prim-ultim>=2) prim--;
            st[++prim]=i;
        }

  }
fprintf (g,"%d\n",prim-1);

for (i=1;i<=prim-1;i++) fprintf (g,"%0.6f %0.6f\n",a[st[i]].x,a[st[i]].y);

    return 0;
}