Cod sursa(job #1464880)

Utilizator TeodorescuStefanEduardTeodorescu Stefan Eduard TeodorescuStefanEduard Data 25 iulie 2015 22:08:26
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <stdio.h>
#include <algorithm>
#include <vector>
#define MAX 120005
using namespace std;
 
typedef struct{
    double x, y;
} Punct;
 
int n, m, i, best;
Punct p[MAX], stack[MAX];
 
double ccw(const Punct& p1, const Punct& p2, const Punct& p3){
    return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}
 
int compare(const Punct& r, const Punct& q){
    return ccw(p[0], r, q) < 0;
}
 
int main(){
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    scanf("%d", &n);
    for(i = 0; i < n; i++){
        scanf("%lf%lf", &p[i].x, &p[i].y);
        if(p[best].y > p[i].y)
            best = i;
        else if(p[best].y == p[i].y)
            if(p[best].x > p[i].x)
                best = i;
    }
    swap(p[0], p[best]);
    sort(p + 1, p + n, compare);
 
    m = 1;
    stack[0] = p[0];
    stack[1] = p[1];
    for(i = 2; i < n; i++){
        while(m >= 1 && ccw(stack[m - 1], stack[m], p[i]) > 0)
            m--;
        stack[++m] = p[i];
    }
 
    printf("%d\n", m + 1);
    for(i = m; i >= 0; i--)
        printf("%lf %lf\n", stack[i].x, stack[i].y);
    return 0;
}