Cod sursa(job #2044397)

Utilizator matdibuDibu Matei matdibu Data 21 octombrie 2017 09:50:01
Problema Infasuratoare convexa Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <bits/stdc++.h>
#define nmax 120003
using namespace std;

struct punct{
    double x, y;
};

punct a[nmax];

int n;

int st[nmax], top;

bool v[nmax];

double F(int i, int j, int p){
    /// <0 daca a[p] este in semiplanul -
    /// al dreptei [a[i],a[j]]
    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 Citire(){
    int i;
    ifstream f("infasuratoare.in");
    f >> n;
    for(i = 1; i <= n; i++)
        f>>a[i].x>>a[i].y;
    f.close();
}

inline bool Compare(punct A, punct B){
    if(A.y == B.y)
        return A.x < B.x;
    return A.y < B.y;
}

///Hill's algorithm
void Hill(){
    int i;
    sort(a+1, a+n+1, Compare);
    st[++top] = 1;
    st[++top] = 2;
    //v[1] = v[2] = true;
    v[2] = true;
    for(i=3; i<=n; i++) {
        while(top>1 && F(st[top-1], st[top], i)<0) {
            v[top] = false;
            top--;
        }
        st[++top] = i;
        v[i] = true;
    }
    for(i=n-1; i>=1; i--){
        if(!v[i]){
            while(F(st[top-1], st[top], i)<0) {
                v[top] = false;
                top--;
            }
            st[++top] = i;
            v[i] = true;
        }
    }
}

void Afisare(){
    int i;
    ofstream g("infasuratoare.out");
    g << top-1 << '\n';
    for(i = 1; i<top; i++)
        g << setprecision(12) << fixed << a[st[i]].x << ' ' << a[st[i]].y << '\n';
}

int main(){
    Citire();
    Hill();
    Afisare();
    return 0;
}