Cod sursa(job #1773363)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 7 octombrie 2016 19:27:56
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <fstream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
#define pi 3.1415926535897
using namespace std;

ofstream g("infasuratoare.out");

long n, sav;

struct point{
    double x, y;
}H[120005];

vector<point> st;

double unghi(point A)
{
    double a;
    if (A.x >= st[0].x && A.y >= st[0].y)
        a = atan((A.x - st[0].x)/(A.y - st[0].y));
    else if (A.x >= st[0].x && A.y <= st[0].y)
        a = pi - atan((A.x - st[0].x)/(st[0].y - A.y));
    else if (A.x <= st[0].x && A.y <= st[0].y)
        a = atan((st[0].x - A.x)/(st[0].y - A.y)) + pi;
    else
        a = 2*pi - atan((st[0].x - A.x)/(A.y - st[0].y));
    return a;
}

bool comp(point A, point B)
{
    double a = unghi(A);
    double b = unghi(B);

    return a<b;
}

double ecd(point A,point B,point C)
{
    return (C.x-A.x)*(B.y-A.y) - (C.y-A.y)*(B.x-A.x);
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    scanf("%ld",&n);


    sav = 1;
    for (int i = 1; i <= n; i++)
    {
        scanf("%lf%lf", &H[i].x, &H[i].y);
        if (H[i].x < H[sav].x)
            sav = i;
    }

    st.push_back(H[sav]);

    for (int i = sav; i <= n; i++)
        H[i] = H[i+1];
    n--;

    sort(H+1, H+n+1, comp);


    for (int i = 1; i <= n; i++)
    {
        if (ecd(st[st.size()-2],st[st.size()-1],H[i])<1)
            st.pop_back();
        st.push_back(H[i]);
    }

    g<<fixed;
    g<<st.size()<<'\n';
    g<<setprecision(6);
    for (int i = st.size()-1; i >= 0; i--)
        g<<st[i].x<<' '<<st[i].y<<'\n';
    return 0;
}