Cod sursa(job #1776103)

Utilizator medicinedoctoralexandru medicinedoctor Data 10 octombrie 2016 22:32:37
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.87 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#define as a.size()
#define hs h.size()

using namespace std;

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

vector <point> h,a;

void qs(int le,int ri)
{
    int i=le, j=ri; point p=a[(i+j)/2];
    while (i<j)
    {
        while (a[i].a<p.a) i++;
        while (a[j].a>p.a) j--;
        if (i<=j)
        {
            swap(a[i],a[j]);
            i++; j--;
        }
    }
    if (i<ri) qs(i,ri);
    if (le<j) qs(le,j);
}

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

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 comp(point a, point b)
{
    if (a.a<b.a) return true; else return false;
}

void ca()
{
    double x,y;
    for (int i=0,q=as; i<q; 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);
    }
}

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

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

main()
{
    lire();
    ca();
    qs(0,as-1);
    hull();
    ecrire();
}