Cod sursa(job #2405842)

Utilizator StefanManolacheManolache Stefan StefanManolache Data 15 aprilie 2019 01:27:09
Problema Infasuratoare convexa Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.41 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

FILE *fin = fopen("infasuratoare.in", "r");
FILE *fout = fopen("infasuratoare.out", "w");

#define MAXN 120000
#define EPS 0.000000000001
#define INF 1000000001

std::vector <int> st;



struct point{
    double x, y;
};

point minn;

struct line{
    double m;
    double n;
};

bool eq(double a, double b) {
    if (abs(b - a) < EPS)
        return 1;
    return 0;
}

void twopointline(point a, point b, double &m, double &n) {
    if (eq(a.x, b.x)) {
        m = INF;
        n = a.x;
    }
    else {
        m = (a.y - b.y) / (a.x - b.x);
        n = a.y - m * a.x;
    }
}

bool cmp(point a, point b) {
    double u = (a.y - minn.y) * (b.x - minn.x);
    double v = (b.y - minn.y) * (a.x - minn.x);
    if (a.x == minn.x && a.y == minn.y)
        return 1;
    if (b.x == minn.x && b.y == minn.y)
        return 0;
    if(eq(u, v)) {
        if (a.x <= b.x)
            return 1;
        return 0;
    }
    else if(u < v)
        return 1;
    return 0;
}

bool verif(point a, point b, point c) {
    bool ok = 1;
    line l1, l2;
    twopointline(a, c, l1.m, l1.n);
    twopointline(b, minn, l2.m, l2.n);
    if (l1.m < l2.m) {
        line aux = l1;
        l1 = l2;
        l2 = aux;
    }
    if ((l1.m - l2.m) * minn.x > l2.n - l1.n) {
        ok = 0;
    }
    if ((l1.m - l2.m) * b.x < l2.n - l1.n) {
        ok = 0;
    }
    return ok;
}

point p[MAXN + 1];

int main()
{
    int n;
    int m = 0;
    fscanf(fin, "%d", &n);
    p[0].x = INF;
    for (int i = 1; i <= n; i++) {
        double x, y;
        fscanf(fin, "%lf%lf", &x, &y);
        p[i].x = x;
        p[i].y = y;
        if (eq(x, p[m].x)) {
            if (y < p[m].y)
                m = i;
        }
        else if (x < p[m].x)
            m = i;
    }
    minn.x = p[m].x;
    minn.y = p[m].y;
    std::sort(p + 1, p + n + 1, cmp);
    st.push_back(1);
    st.push_back(2);
    st.push_back(3);
    for (int i = 4; i <= n; i++) {
        int siz = st.size();
        while (!verif(p[st[siz - 2]], p[st[siz - 1]], p[i])) {
            st.pop_back();
            siz--;
        }
        st.push_back(i);
    }
    int siz = st.size();
    fprintf(fout, "%d\n", siz);
    for (int i = 0; i < siz; i++) {
        fprintf(fout, "%lf %lf\n", p[st[i]].x, p[st[i]].y);
    }
    return 0;
}