Cod sursa(job #2166607)

Utilizator mirupetPetcan Miruna mirupet Data 13 martie 2018 17:57:44
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;

FILE *fin = freopen("infasuratoare.in", "r", stdin);
FILE *fout = freopen("infasuratoare.out", "w", stdout);

const int NMax = 120002;
int N, ind;
double minX = 1000000000, minY = 1000000000;
struct point {double x, y;} v[NMax], sol[NMax];

double aria(point A, point B, point C){

    return A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y);
}

inline bool cmp(point A, point B){

    return (aria(v[1], A, B) > 0);
}

int main(){

    scanf("%d", &N);

    for (int i = 1; i <= N; i++){

        scanf("%lf%lf", &v[i].x, &v[i].y);
        if (v[i].y < minY || (v[i].y == minY && v[i].x < minX)){

            minY = v[i].y;
            minX = v[i].x;
            ind = i;
        }
    }

    swap(v[1], v[ind]);
    sort(v + 2, v + N + 1, cmp);

    for (int i = 1; i < 4; i++)
        sol[i] = v[i];
    int card = 3;

    for (int i = 4; i <= N; i++){

        while (card && aria(sol[card - 1], sol[card], v[i]) < 0)
            card --;
        sol[++ card] = v[i];
    }

    printf("%d\n", card);

    for (int i = 1; i <= card; i++)
        printf("%.12f %.12f\n", sol[i].x, sol[i].y);
}