Cod sursa(job #1776560)

Utilizator medicinedoctoralexandru medicinedoctor Data 11 octombrie 2016 15:40:07
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <cmath>
#include <fstream>
#include <vector>
#include <iomanip>
#define as a.size()
#define hs h.size()

using namespace std;

struct point {
   double x,y,a;
} mp;

vector <point> a,h;

void lire()
{
    ifstream f("zzz.in");
    int n; point p;
    f >> n >> mp.x >> mp.y;
    a.push_back(mp);
    for (int i=1; i<n ; i++)
    {
        f >> p.x >> p.y;
        if (p.x<mp.x || p.x==mp.x && p.y<mp.y) mp;
        a.push_back(p);
    }
}

void ca()
{
    double x,y;
    for (int i=0; i<as; i++)
    {
        x=a[i].x-mp.x;
        y=a[i].y-mp.y;
        if (x==0 && y==0) a[i].a=1.1;
        else a[i].a=y*abs(y)/(x*x+y*y);
    }
}

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

bool cA(point a, point b)
{
    if (a.a<b.a) return true; else return false;
}

void hull()
{
    for (int i=0; i<4; i++)
    {
        h.push_back(a[i]);
    }
    if (det(h[0],h[1],h[2])<=0)
    {
        h[1]=h[2];
        h.pop_back();
    }
    for (int i=3; i<as; i++)
    {
        h.push_back(a[i]);
        while (hs>2 && det(h[hs-3],h[hs-2],h[hs-1])<=0)
        {
            h[hs-2]=h[hs-1];
            h.pop_back();
        }
    }
}

void ecrire()
{
    ofstream f("zzz.out");
    f << fixed;
    f << hs << '\n';
    for (int i=0; i<hs; i++)
    {
        f << setprecision(9) << h[i].x << ' ' << h[i].y << '\n';
    }
}

main()
{
    lire();
    ca();
    sort(a.begin(),a.end(),cA);
    hull();
    ecrire();
}