Cod sursa(job #1131722)

Utilizator radu2004GOLD radu radu2004 Data 1 martie 2014 07:38:42
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>
#define y first
#define x second
using namespace std;
typedef pair  <double,double> punct;
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;}
}




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 (a+1,a+n+1);
 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]]) ) 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;
}