Cod sursa(job #1703535)

Utilizator refugiatBoni Daniel Stefan refugiat Data 17 mai 2016 06:35:44
Problema Infasuratoare convexa Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
//#include <iostream>
//#include <fstream>
#include <algorithm>
#include <cstdio>
#define pct pair<double,double>

using namespace std;
FILE* si=fopen("infasuratoare.in","r");
FILE* so=fopen("infasuratoare.out","w");
//ifstream si("infasuratoare.in");
//ofstream so("infasuratoare.out");
const int NMAX=120005;
pct v[NMAX];
double det(pct a,pct b,pct c)
{
    return ((a.first-b.first)*(a.second-c.second)-(a.first-c.first)*(a.second-b.second));
}
bool comp(pct a,pct b)
{
    return (det(v[0],a,b)<0);
}
int sol[NMAX];
int main()
{
    int n;
    fscanf(si,"%i",&n);
    int i;
    for(i=0;i<n;++i)
    {
        fscanf(si,"%lf %lf",&v[i].first,&v[i].second);
        //cout<<v[i].first<<' '<<v[i].second<<'\n';
    }
    for(i=1;i<n;++i)
    {
        if(v[i]<v[0])
            swap(v[i],v[0]);
    }
    sort(v,v+n,comp);
    int nr=0;
    for(i=0;i<n;++i)
    {

        while(nr>=2&&det(v[sol[nr-2]],v[sol[nr-1]],v[i])>0) nr--;
        sol[nr]=i;
        ++nr;

    }
    fprintf(so,"%i\n",nr);
    for(i=nr-1;i>=0;--i)
        fprintf(so,"%f %f\n",v[sol[i]].first,v[sol[i]].second);
    return 0;
}