Cod sursa(job #2628254)

Utilizator redstonegamer22Andrei Ion redstonegamer22 Data 15 iunie 2020 11:18:49
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

const int NMAX = 120000;

struct point {
    double x, y;
} v[NMAX+7];

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;
    if(val < 0) return -1;
    return 0;
}

point ll;

bool cmp(point a, point b) {
    if(a.x == ll.x && a.y == ll.y) return 1;
    if(b.x == ll.x && b.y == ll.y) return 0;
    return (ccw(ll, a, b) > 0);
}

int stck[NMAX+7];
int top = 0;

int main() {
    int n; in >> n;
    in >> v[1].x >> v[1].y;

    ll = v[1];
    for(int i = 2; i <= n; i++) {
        in >> 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[stck[top-1]], v[stck[top]], v[i])<=0) {
            top--;
        }
        top++;
        stck[top]= i;
    }

    while(top >= 2 && ccw(v[stck[top-1]], v[stck[top]], v[0])<=0) {
        top--;
    }
    top++;
    stck[top]= 0;

    top--;

    out << top << "\n";

    for(int i = 1; i <= top; i++) {
        out << fixed << setprecision(6) << v[stck[i]].x << " " << v[stck[i]].y << "\n";
    }

    return 0;
}