Cod sursa(job #1960493)

Utilizator PescaruVictorPescaru Victor PescaruVictor Data 10 aprilie 2017 14:22:22
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.32 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define NMAX 120010
#define PI 3.14159265

using namespace std;

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

struct puncte
{
    double x, y, d, unghi;
};

int n, vf;
puncte pct[NMAX], s[NMAX];

void citire();
void rez();
double dist (puncte a, puncte b);
double munghi (puncte a, puncte b);
double rot (puncte a, puncte b, puncte c);
bool cmp(puncte a, puncte b);
void afisare();
double modul (double a);


int main()
{
    citire();
    rez();
    afisare();
    return 0;
}

void citire()
{
    int i;
    fin>>n;
    for(i=1; i<=n; ++i)
        fin>>pct[i].x>>pct[i].y;
}

void rez ()
{
    int i, pmin=1;

    for(i=1; i<=n; ++i)
        if(pct[i].y < pct[pmin].y)
            pmin=i;
        else if(pct[i].y == pct[pmin].y && pct[i].x < pct[pmin].x)
            pmin=i;
    for(i=1; i<=n; ++i)
    {
        pct[i].d=dist(pct[i], pct[pmin]);
        pct[i].unghi=munghi(pct[i], pct[pmin]);
    }

    sort (pct+1, pct+n+1, cmp);

    vf=0;
    s[++vf]=pct[1];
    s[++vf]=pct[2];

    for(i=3; i<=n; ++i)
    {
        s[++vf]=pct[i];
        while ( rot(s[vf-2], s[vf-1], s[vf] ) < 0 && vf > 2 )
        {
            s[vf-1]=s[vf--];
        }
    }
}

double rot (puncte a, puncte b, puncte c)
{
    return a.x*b.y+a.y*c.x+b.x*c.y-c.x*b.y-a.y*b.x-a.x*c.y;
}

bool cmp(puncte a, puncte b)
{
    return ( (a.unghi<b.unghi) || (a.unghi==b.unghi && a.d<b.d) );
}

double dist (puncte a, puncte b)
{
    return sqrt ( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
}

double munghi (puncte a, puncte b)
{
    double aux=atan( (b.y-a.y) / (b.x-a.x) ) *180 / PI;
    if(aux<0)
        return 180+aux;
    return aux;
}

double modul (double a)
{
    if(a<0)
        return -a;
    return a;
}

void afisare()
{
    int i, pmin=1;
    fout<<vf<<'\n';

    for(i=1; i<=vf; ++i)
        if(s[i].x < s[pmin].x)
            pmin=i;
        else if(s[i].x == s[pmin].x && s[i].y < s[pmin].y)
            pmin=i;
    for(i=pmin; i<=vf; ++i)
        fout<<setprecision(12)<<fixed<<s[i].x<<' '<<setprecision(12)<<fixed<<s[i].y<<'\n';
    for(i=1; i<pmin; ++i)
        fout<<setprecision(12)<<fixed<<s[i].x<<' '<<setprecision(12)<<fixed<<s[i].y<<'\n';
}