Cod sursa(job #1826554)

Utilizator vazanIonescu Victor Razvan vazan Data 10 decembrie 2016 16:49:04
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.58 kb
#include<cstdio>
#include<algorithm>
using namespace std;
const double eps = 1.e-12;
const int NMAX = 120100;
const double inf = 1.e9 + 1;
struct Point {
    double x, y;
};

double panta(Point x, Point y){
    if(y.x == x.x)
        return inf;
    return (y.y - x.y) / (y.x - x.x);
}

int cadran(Point x, Point y){
    Point ty;
    ty.x = y.x - x.x;
    ty.y = y.y - x.y;
    if(ty.x >= 0 && ty.y > 0)
        return 1;
    else if(ty.x < 0 && ty.y >= 0)
        return 2;
    else if(ty.x <= 0 && ty.y < 0)
        return 3;
    else if(ty.x > 0 && ty.y <= 0)
        return 4;
}

Point gl_LL;
int cmp(Point x, Point y){
    if(panta(gl_LL, x) - panta(gl_LL, y) < eps)
        return 1;
    return 0;
}

int solve(Point *p, int *sol, int n){
    int LL = 1;
    for(int i = 1; i <= n; i++){
        if(p[i].y < p[LL].y)
            LL = i;
        else if(p[i].y == p[LL].y && p[i].x < p[LL].x)
            LL = i;
    }
    swap(p[LL], p[1]);
    gl_LL = p[1];
    int q1 = 0, q2 = 0;
    Point c1[NMAX], c2[NMAX];
    for(int i = 2; i <= n; i++)
        if(panta(gl_LL, p[i]) < 0)
            c2[++q2] = p[i];
        else
            c1[++q1] = p[i];
    sort(c1 + 1, c1 + q1 + 1, cmp);
    sort(c2 + 1, c2 + q2 + 1, cmp);
    for(int i = 2; i <= q1 + 1; i++)
        p[i] = c1[i - 1];
    for(int i = q1 + 2; i <= q1 + q2 + 1; i++)
        p[i] = c2[i - q1 - 1];
    int cr = 1;
    sol[cr++] = 1;
    sol[cr] = 2;
    bool b;
    for(int i = 3; i <= n; i++){
        b = 1;
        while(b){
        /*while((cadran(p[sol[cr - 1]], p[sol[cr]]) > cadran(p[sol[cr]], p[i])) &&
              (panta(p[sol[cr - 1]], p[sol[cr]]) - panta(p[sol[cr]], p[i]) > eps))*/
            if((cadran(p[sol[cr - 1]], p[sol[cr]]) < cadran(p[sol[cr]], p[i])))
                b = 0;
            else if( (cadran(p[sol[cr - 1]], p[sol[cr]]) == cadran(p[sol[cr]], p[i]))&& (panta(p[sol[cr - 1]], p[sol[cr]]) - panta(p[sol[cr]], p[i]) < -eps))
                b = 0;
            if(b) cr--;
        }
        cr++;
        sol[cr] = i;
    }
    return cr;
}

int main(){
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    int v[NMAX], n, x;
    double tx, ty;
    Point p[NMAX];
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%lf%lf", &tx, &ty);
        p[i].x = tx;
        p[i].y = ty;
    }
    x = solve(p, v, n);
    printf("%d\n", x);
    for(int i = 1; i <= x; i++){
        tx = p[v[i]].x;
        ty = p[v[i]].y;
        printf("%.6lf %.6lf\n", tx, ty);
    }
    return 0;
}