Cod sursa(job #451763)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 9 mai 2010 21:59:28
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.31 kb
# include <cstdio>
# include <algorithm>

using namespace std;

# define FIN "infasuratoare.in"
# define FOUT "infasuratoare.out"
# define x first
# define y second
# define MAX_N 120005

int Stack[MAX_N];
int N, i, j, vf;
pair <double, double> Pol[MAX_N];
    
    int cmp1(pair <double, double> A, pair <double, double> B) {
        
        return (A.y - Pol[1].y) * (B.x - Pol[1].x) < (B.y - Pol[1].y) * (A.x - Pol[1].x);
    }
    
    int cmp2(pair <double, double> A, pair <double, double> B) {
        
        return A.y > B.y;
    }
    
    int parte(int i, int j, int k) {
        return ((Pol[i].x - Pol[k].x) * (Pol[j].y - Pol[k].y) - (Pol[i].y - Pol[k].y) * (Pol[j].x - Pol[k].x) > 0);
    }
    
    void convex() {
        
        int i, j, bnd, pleft;
        
        pleft = 1;
        for (i = 1; i <= N; ++i)
           if ((Pol[pleft].x == Pol[i].x && Pol[pleft].y > Pol[i].y) || Pol[pleft].x > Pol[i].x) pleft = i;
        
        pair <double, double> aux = Pol[pleft]; Pol[pleft] = Pol[1]; Pol[1] = aux;
        
        i = 2; j = N;
        while (i <= j) {
              
            while (Pol[i].x != Pol[1].x && i <= N) ++i;
            while (Pol[j].x == Pol[1].x && j >= 2) --j;
            
            if (i < j)
               aux = Pol[i], Pol[i] = Pol[j], Pol[j] = aux;
        }
        
        for (bnd = 2; bnd <= N && Pol[bnd].x != Pol[1].x; ++bnd);
        
        sort(Pol + 2, Pol + bnd, cmp1);
        if (bnd <= N) sort(Pol + bnd + 1, Pol + N + 1, cmp2);
        
        //for (i = 1; i <= N; ++i) printf("%lf %lf\n", Pol[i].x, Pol[i].y);
        
        --bnd; Stack[vf = 1] = 1;
        for (i = 2; i <= N; ++i) {
            if (vf < 2) {
                Stack[++vf] = i;
                continue;
            }
            
            while (vf >= 2 && !parte(Stack[vf - 1], Stack[vf], i)) --vf;
            Stack[++vf] = i;
        }       
    }

    int main() {
        freopen(FIN, "r", stdin);
        freopen(FOUT, "w", stdout);
        
        scanf("%d", &N);
        for (i = 1; i <= N; ++i) scanf("%lf%lf", &Pol[i].x, &Pol[i].y);
        
        convex();
        
        printf("%d\n", vf);
        for (i = 1; i <= vf; ++i) printf("%lf %lf\n", Pol[Stack[i]].x, Pol[Stack[i]].y);
        
        return 0;
    }