Cod sursa(job #1130629)

Utilizator lehman97Dimulescu David lehman97 Data 28 februarie 2014 14:30:18
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <stdio.h>
#include <algorithm>
#define MAX_N 120005

using namespace std;

FILE *f=fopen("infasuratoare.in","r");
FILE *g=fopen("infasuratoare.out","w");



int n,i,j,k,st[MAX_N];

struct vec
{
    double x,y;
}mn,v[MAX_N],aux;

int semn(vec a,vec b,vec c)
{
double s;
s=(long double)a.x*b.y+ b.x*c.y+ c.x*a.y - a.y*b.x- b.y*c.x- c.y*a.x;
if (s<0) return 0;
return 1;

}


bool cmp(vec a,vec b)
{
    return ((a.y-mn.y)*(b.x-mn.x)<=(a.x-mn.x)*(b.y-mn.y));
}



int main()
{
      fscanf(f,"%d",&n);
      for(i=1;i<=n;i++)
      fscanf(f,"%lf%lf",&v[i].x,&v[i].y);
      mn.x=v[1].x;
      mn.y=v[1].y;
      for(j=2;j<=n;j++)
      if(v[j].x<mn.x || (v[j].x==mn.x && v[j].y<mn.y)){mn=v[j];k=j;}
      vec aux=v[1];
      v[1]=v[k];
      v[k]=aux;
      sort(v+1,v+n+1,cmp);
      st[0]=2;
      st[1]=1;
      st[2]=2;
      for(i=3;i<=n;i++)
        {
          while(st[0]>=2 && !semn(v[st[st[0]-1]],v[st[st[0]]],v[i])) st[0]--;
          st[0]++;
          st[st[0]]=i;
    }
    fprintf(g,"%d\n",st[0]);
    for(i=1;i<=st[0];i++)
    fprintf(g,"%lf %lf\n",v[st[i]].x,v[st[i]].y);
    fclose(g);
    return 0;
}