Cod sursa(job #1913767)

Utilizator FlowstaticBejan Irina Flowstatic Data 8 martie 2017 13:57:03
Problema Invers modular Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#define INF 1000000000
#define NMAX 120005
using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct punct
{
    double x,y;
}pct[NMAX],mini,st[NMAX];
int N;
double Aria(punct a, punct b, punct c)
{
    return (a.x - b.x) * (c.y - b.y) - (a.y - b.y) * (c.x - b.x);
}

int comp(const punct& a, const punct& b)
{
    return (Aria(a,mini,b) > 0);
}

int main()
{
    int i,poz;
    fin>>N;

    mini.x = mini.y = INF;
    for(i=1; i<=N; i++)
    {
        fin>>pct[i].x>>pct[i].y;
        if(pct[i].x < mini.x)
        {
            mini = pct[i];
            poz = i;
        }
        else if(pct[i].x == mini.x && pct[i].y < mini.y)
            mini = pct[i], poz = i;
    }
    swap(pct[1],pct[poz]);

    sort(pct+2,pct+N+1,comp);

    st[1] = mini;
    int po = 2;

    for(i = po; i<=N;i++)
    {
        while(po > 2 && Aria(st[po-2], st[po-1], pct[i])>=0)
            po--;
        st[po] = pct[i];
        po++;
    }

    fout<<po-1<<'\n';
    fout<<setprecision(6)<<fixed;
    for(i=1; i<po; ++i)
        fout<<st[i].x<<" "<<st[i].y<<'\n';
    return 0;
}