Cod sursa(job #2174317)

Utilizator B_RazvanBaboiu Razvan B_Razvan Data 16 martie 2018 11:35:19
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#define NMAX 120005

using namespace std;

int N, st[NMAX], top;
bool viz[NMAX];
struct Point {
    double x, y;
}a[NMAX];

bool cmp(Point A, Point B) {
    if(A.y == B.y) {
        return A.x < B.x;
    }
    return A.y < B.y;
}

void read() {
    scanf("%d", &N);
    for(int i = 1; i <= N; ++i) {
        scanf("%lf %lf", &a[i].x, &a[i].y);
    }
    sort(a + 1, a + N + 1, cmp);
}

double det(int i, int j, int p) {
    return a[p].x * (a[i].y - a[j].y) +
            a[p].y * (a[j].x - a[i].x) +
            a[i].x * a[j].y - a[j].x * a[i].y;
}

void insertInStack(int poz) {
    while(top > 1 && det(st[top - 1], st[top], poz) < 0) {
        viz[st[top]] = false;
        top--;
    }
    viz[poz] = true;
    st[++top] = poz;
}

void solve() {
    st[1] = 1;
    viz[2] = true;
    st[2] = 2;
    top = 2;
    for(int i = 3; i <= N; ++i) {
        insertInStack(i);
    }
    for(int i = N - 1; i >= 1; --i) {
        if(!viz[i]) {
            insertInStack(i);
        }
    }
}

void print() {
    printf("%d\n", top - 1);
    for(int i = 1; i < top; ++i) {
        printf("%.13lf %.13lf\n", a[st[i]].x, a[st[i]].y);
    }
}

int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    read();
    solve();
    print();
    return 0;
}