Cod sursa(job #2405979)

Utilizator StefanManolacheManolache Stefan StefanManolache Data 15 aprilie 2019 11:38:40
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.26 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;

void swap(point &a, point &b) {
    point aux = a;
    a = b;
    b = aux;
}

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


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) {
    if (a.x < c.x)
        swap(a, c);
    double t = (a.y - c.y) * (b.x - minn.x) - (b.y - minn.y) * (a.x - c.x);
    double s = (b.y - a.y) * (b.x - minn.x) * (a.x - c.x) - (b.y - minn.y) * (a.x - c.x) * b.x + (a.y - c.y) * (b.x - minn.x) * a.x;
    if (t < 0) {
        t = -t;
        s = -s;
    }
    if (t * minn.x > s)
        return 0;
    if (t * b.x < s)
        return 0;
    return 1;
}

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);
    for (int i = 3; 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;
}