Cod sursa(job #1929061)

Utilizator 1475369147896537415369Andrei Udriste 1475369147896537415369 Data 17 martie 2017 00:19:12
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <cstdio>
#include <algorithm>
using namespace std;

struct point{
    double x;
    double y;
};

int N, index = 1;
point input[120001], hull[120001];

inline double cross(const point &p1, const point &p2, const point &p3){
    return p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y - p2.y);
}
inline bool comparator(const point &p1, const point &p2){
    return cross(input[1], p1, p2) > 0;
}

int main(){

    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);

    scanf("%d", &N);

    for(int i = 1; i <= N; i++){
        scanf("%lf %lf", &input[i].x, &input[i].y);
        if(input[i].y < input[index].y || input[i].y == input[index].y && input[i].x < input[index].x){
            index = i;
        }
    }
    swap(input[1], input[index]);
    sort(input + 2, input + N + 1, comparator);

    hull[1] = input[1];
    hull[2] = input[2];

    index = 2;

    for(int i = 3; i <= N; i++){
        while(index >= 2 && cross(hull[index - 1], hull[index], input[i]) <= 0){
            index--;
        }hull[++index] = input[i];
    }printf("%d\n", index);

    for(int i = 1; i <= index; i++){
        printf("%.12lf %.12lf\n", hull[i].x, hull[i].y);
    }
    return 0;
}