Cod sursa(job #1130685)

Utilizator lehman97Dimulescu David lehman97 Data 28 februarie 2014 14:50:07
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <stdio.h>;
#include <algorithm>;
using namespace std;

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

int n;
struct punct {
double x,y;
};
punct mn,v[120001];
int q,i,st[120001];


int semn(punct a,punct b, punct 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(punct a,punct 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);
        if(i==1) mn=v[i];
        if(mn.x>v[i].x)
        {
            mn=v[i];
            q=i;

        }else
        if(mn.x==v[i].x&& v[i].y<mn.y)
        {
            mn=v[i];
            q=i;
        }


    }

    punct ax=v[1];
    v[1]=v[q];
    v[q]=ax;
    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;
}