Cod sursa(job #1142374)

Utilizator RadEmanuelRad Emanuel RadEmanuel Data 13 martie 2014 19:27:56
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include<fstream>
#include<algorithm>
#include<iomanip>
#define INF 21000000
#define DMAX 12000
using namespace std;

ifstream fin ("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,spoz,i,k;
struct punct{double x,y;}st[DMAX],v[DMAX],b[DMAX];

int cmp(punct a, punct b)
{
    double m1,m2;
    if(a.x==v[0].x) m1=INF;
               else m1=(a.y-v[0].y)/(a.x-v[0].x);
    if(b.x==v[0].x) m2=INF;
               else m2=(b.y-v[0].y)/(b.x-v[0].x);
    return m1<m2;
}

void merge_sort(int st, int dr)
{
    if(st==dr)
        return;
    int mij=(st+dr)/2;
    merge_sort(st,mij);
    merge_sort(mij+1,dr);

    int i=st,k=st,j=mij+1;
    while(i<=mij && j<=dr)
        if(cmp(v[i],v[j]))
            b[k++]=v[i++];
        else
            b[k++]=v[j++];
    if(i<=mij)
        for(;i<=mij;++i)
            b[k++]=v[i];
    else
        for(;j<=dr;++j)
            b[k++]=v[j];
    for(k=st;k<=dr;k++)
        v[k]=b[k];
}

int calc(punct A, punct B, punct C){return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);}

int main()
{
    fin>>n;
    for(i=0;i<n;++i)
    {
        fin>>v[k].x;
        fin>>v[k].y;
        ++k;
        if(v[i].x<v[spoz].x || (v[i].x==v[spoz].x && v[i].y<v[spoz].y))
            spoz=i;
    }
    swap(v[0],v[spoz]);
    merge_sort(1,n-1);
    st[1]=v[0];
    st[2]=v[1];
    int niv=2;
    for(i=2;i<n;++i)
    {
        while(niv>=2 && calc(st[niv-1],st[niv],v[i])<=0)
            --niv;
        st[++niv]=v[i];
    }
    fout<<niv<<'\n';
    for(i=1;i<=niv;++i)
        fout<<setprecision(12)<<st[i].x<<" "<<st[i].y<<'\n';
    return 0;
}