Cod sursa(job #2628527)

Utilizator alexradu04Radu Alexandru alexradu04 Data 16 iunie 2020 11:27:50
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <bits/stdc++.h>

using namespace std;

struct POINT {
    double x, y;
} v[120007];

int ccw(POINT a, POINT b, POINT c) {
    double val = a.x * b.y - a.y * b.x + b.x * c.y - b.y * c.x + c.x * a.y - c.y * a.x;
    if (val > 0)
        return 1;
    else
    if (val < 0)
        return -1;
    else
    return 0;
}
POINT ll;

bool cmp(POINT a, POINT b) {
    if (a.x == ll.x && a.y == ll.y)
        return true;
    else if (b.x == ll.x && b.y == ll.y)
        return false;
    else
        return (ccw(ll, a, b) > 0);
}

int st[120007];
int top = 0;

int main() {
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int n;
    scanf("%d ", &n);
    scanf("%lf %lf", &v[1].x, &v[1].y);
    ll = v[1];
    for (int i = 2; i <= n; i++) {
        scanf("%lf %lf", &v[i].x, &v[i].y);
        if (v[i].x == ll.x) {
            if (v[i].y < ll.y)
                ll = v[i];
        } else if (v[i].x < ll.x) {
            ll = v[i];
        }
    }
    sort(v + 1, v + n + 1, cmp);
    for (int i = 1; i <= n; i++) {
        while (top >= 2 && ccw(v[st[top - 1]], v[st[top]], v[i]) <= 0) {
            top--;
        }
        top++;
        st[top] = i;
    }
    while (top >= 2 && ccw(v[st[top - 1]], v[st[top]], v[0]) <= 0) {
        top--;
    }
    top++;
    st[top] = 0;
    top--;
    printf("%d\n", top);
    for (int i = 1; i <= top; i++) {
        printf("%lf %lf\n", v[st[i]].x, v[st[i]].y);
    }
    return 0;
}