Cod sursa(job #1051278)

Utilizator impulseBagu Alexandru impulse Data 9 decembrie 2013 21:37:07
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
//
//  main.cpp
//  infasuratoare
//
//  Created by Alexandru Bâgu on 12/9/13.
//  Copyright (c) 2013 Alexandru Bâgu. All rights reserved.
//

#define MAX 120001

#include <stdio.h>
#include <algorithm>

typedef struct pct {
    double x, y;
} point;

point pts[MAX];

int swap(point *p1, point *p2)
{
    point p = *p1;
    *p1 = *p2;
    *p2 = p;
    return 0;
}

double delta(point p1, point p2, point p3)
{
    return (p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x);
}

int cmp(point p1, point p2)
{
    return (delta(pts[0], p1, p2) < 0);
}

int main(int argc, const char * argv[])
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    
    int S[MAX];
    int n, i;
    scanf("%d", &n);
    for(i = 0; i < n; i++)
    {
        scanf("%lf %lf", &pts[i].x, &pts[i].y);
        S[i] = 0;
    }
    
    int k = 0;
    for(i = 1; i < n; i++)
        if((pts[i].x < pts[k].x) || (pts[i].x == pts[k].x && pts[i].y < pts[k].y))
            k = i;
    swap(pts, pts + k);
    
    std::sort(pts + 1, pts + n, cmp);

    S[0] = 0;
    S[1] = 1;
    int N = 1;
    for(i = 2; i < n; i++)
    {
        while(delta(pts[S[N-1]], pts[S[N]], pts[i]) > 0 && N >= 1) N--;
        N++;
        S[N] = i;
    }
    printf("%d \n", N+1);
    for(i = N; i >= 0; i--)
        printf("%lf %lf\n", pts[S[i]].x, pts[S[i]].y);
    return 0;
}