Cod sursa(job #1051273)

Utilizator impulseBagu Alexandru impulse Data 9 decembrie 2013 21:34:00
Problema Infasuratoare convexa Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 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>

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

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

double areasz(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, point p3)
{
    return (areasz(p1, p2, p3) < 0);
}

int sort(point* v, int s, int d)
{
    if(s >= d - 1) return 0;
    int a = s, b = d, w = 1;
    while(a < b)
    {
        if(cmp(v[0], v[a], v[b]))
        {
            if(w) a ++;
            else b--;
        }
        else
        {
            swap(v+a, v+b);
            w ^= 1;
        }
    }
    sort(v, s, a - 1);
    sort(v, a + 1, d);
    return 0;
}

int main(int argc, const char * argv[])
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    
    point pts[MAX];
    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);
    
    sort(pts, 1, n-1);

    S[0] = 0;
    S[1] = 1;
    int N = 1;
    for(i = 2; i < n; i++)
    {
        while(areasz(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;
}