Cod sursa(job #2139301)

Utilizator mariakKapros Maria mariak Data 22 februarie 2018 13:19:26
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>
#define Point pair <double, double>
#define x first
#define y second
FILE *fin  = freopen("infasuratoare.in", "r", stdin);
FILE *fout = freopen("infasuratoare.out", "w", stdout);

using namespace std;
/*--------Data--------*/
const int MAX = 12e4 + 2;
int n;
Point p[MAX];
int H[MAX], sz;
/*--------------------*/

void Read(){
    scanf("%d", &n);
    for(int i = 0; i < n; ++ i)
        scanf("%lf%lf", &p[i].x, &p[i].y);
}

double Cross(const int &o, const int &a, const int &b){
    Point O = p[o], A = p[a], B = p[b];
    return 1LL * (A.x - O.x) * (B.y - O.y) - 1LL * (A.y - O.y) * (B.x - O.x);
}

void Write(){
    -- sz;
    printf("%d\n", sz);
    for(int i = 0; i < sz; ++ i)
        printf("%.13f %.13f\n", p[H[i]].x, p[H[i]].y);
}

int main(){
    Read();
    sort(p, p + n);

    for(int i = 0; i < n; ++ i){
        while(sz >= 2 && Cross(H[sz - 2], H[sz - 1], i) <= 0)
            -- sz;
        H[sz++] = i;
    }

    for(int i = n - 2, t = sz + 1; i >= 0; -- i){
        while(sz >= t && Cross(H[sz - 2], H[sz - 1], i) <= 0)
            -- sz;
        H[sz++] = i;
    }

    Write();
    return 0;
}