Cod sursa(job #1773402)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 7 octombrie 2016 20:00:08
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 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,int &cadran)
{
    double a;
    if (A.x >= st[0].x && A.y >= st[0].y)
        a = (A.x - st[0].x)/(A.y - st[0].y),cadran = 1;
    else if (A.x >= st[0].x && A.y <= st[0].y)
        a = -(A.x - st[0].x)/(st[0].y - A.y),cadran = 2;
    else if (A.x <= st[0].x && A.y <= st[0].y)
        a = (st[0].x - A.x)/(st[0].y - A.y),cadran = 3;
    else
        a = -(st[0].x - A.x)/(A.y - st[0].y),cadran = 4;
    return a;
}

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

    if (cadranA == cadranB)
        return a<b;
    return cadranA<cadranB;
}

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++)
    {
        while (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;
}