Cod sursa(job #1889373)

Utilizator nnnmmmcioltan alex nnnmmm Data 22 februarie 2017 18:15:04
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <cstdio>
#include <algorithm>
#include <iostream>

struct punct
{
 double x,y;
};

const int NMAX=120001;

const double INF=1000000001.0,eps=0;

punct v[NMAX],stiva[NMAX];
int marime;
punct punctu_polar;

bool cmp(punct a,punct b)
{
 return (((a.x-punctu_polar.x)*(b.y-punctu_polar.y))-((b.x-punctu_polar.x)*(a.y-punctu_polar.y)))<eps;
}

double Aria(punct A,punct B,punct C)
{
 return (A.x*(B.y-C.y)+B.x*(C.y-A.y)+C.x*(A.y-B.y))/2.0;
}

void infasuratoarea(int n)
{
 std::sort(v+1,v+n+1,cmp);
 marime=2;
 stiva[1]=v[1];
 stiva[2]=v[2];
 for(int i=3;i<=n;i++)
     {
      while(marime>=2 && (stiva[marime].x-stiva[marime-1].x)*(v[i].y-stiva[marime-1].y)-(stiva[marime].y-stiva[marime-1].y)*(v[i].x-stiva[marime-1].x)>eps)
            marime--;
      stiva[++marime]=v[i];
     }
}

int main()
{
 FILE *in=fopen("infasuratoare.in","r");
 int n;
 fscanf(in,"%d ",&n);
 punctu_polar.x=punctu_polar.y=INF;
 for(int i=1;i<=n;i++)
     {
      fscanf(in,"%lf %lf ",&v[i].x,&v[i].y);
      if(v[i].y<punctu_polar.y)
         punctu_polar=v[i];
      else
         if(v[i].y==punctu_polar.y)
            if(v[i].x<punctu_polar.x)
               punctu_polar=v[i];
     }
 fclose(in);
 infasuratoarea(n);
 FILE *out=fopen("infasuratoare.out","w");
 fprintf(out,"%d\n",marime);
 for(int i=marime;i>=1;i--)
     {
      fprintf(out,"%.8f %.8f\n",stiva[i].x,stiva[i].y);
     }
 fclose(out);
 return 0;
}