Cod sursa(job #1280367)

Utilizator danyro364Savu Ioan Daniel danyro364 Data 1 decembrie 2014 21:09:36
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
//#include <iostream>
#include <cstdio>
#include <algorithm>
#define nmax 120001
#define inf 100000000000
using namespace std;
FILE *f=fopen("infasuratoare.in","r"),*g=fopen("infasuratoare.out","w");
struct punct
{
     float x,y;
}v[nmax],p;
int st[nmax],viz[nmax];

float det(punct a, punct b, punct c)
{
    return a.x*(b.y-c.y)-a.y*(b.x-c.x)+b.x*c.y-c.x*b.y;
}
bool comp(punct a, punct b)
{
    return det(a,p,b)>0;
}
int main()
{
    int i,j,n,k,semn=1,poz;
    p.x = inf;
    p.y = inf;
    fscanf(f,"%d",&n);
    for(i=1;i<=n;i++)
        {fscanf(f,"%f %f",&v[i].x,&v[i].y);
            if(v[i].x<p.x)
            {
                p=v[i];
                poz=i;
            }
            if(v[i].x==p.x && v[i].y<p.y)
            {
                p=v[i];
                poz=i;
            }
        }
    swap(v[poz], v[1]);
    sort(v+2,v+1+n,comp);
    st[1]=1;
    k=1; viz[2]=1;
    for(i=2;i<=n;i++)
    {
        while(k>1&&det(v[st[k-1]],v[st[k]],v[i])>=0)
            k--;
        st[++k]=i;
    }
    fprintf(g,"%d\n",k-1);
    for(i=1;i<k;i++)
        fprintf(g,"%.6f %.6f\n",v[st[i]].x,v[st[i]].y);
    return 0;
}