Cod sursa(job #1989858)

Utilizator MaarcellKurt Godel Maarcell Data 9 iunie 2017 11:26:53
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <iomanip>
using namespace std;

#define fi first
#define se second
typedef long long LL;
typedef long double LD;

struct point{
    LD x,y;
};

int N,nxt[120100],prv[120100]; point a[120100];

LD area(point A, point B, point C){
    return (A.x*B.y+B.x*C.y+C.x*A.y-A.y*B.x-B.y*C.x-C.y*A.x);
}

vector<point> gethull(){
    sort(a+1,a+N+1,[](point A, point B) { return A.x < B.x; });
    nxt[1]=prv[1]=2;
    nxt[2]=prv[2]=1;

    int i;
    for (i=3; i<=N; i++){
        if (a[i].y>=a[i-1].y)
            prv[i]=i-1,nxt[i]=nxt[i-1];
        else
            nxt[i]=i-1,prv[i]=prv[i-1];

        prv[nxt[i]]=i,nxt[prv[i]]=i;
        while (i!=nxt[nxt[i]] && area(a[i],a[nxt[i]],a[nxt[nxt[i]]])<0){
            prv[nxt[nxt[i]]]=i;
            nxt[i]=nxt[nxt[i]];
        }
        while (i!=prv[prv[i]] && area(a[prv[prv[i]]],a[prv[i]],a[i])<0){
            nxt[prv[prv[i]]]=i;
            prv[i]=prv[prv[i]];
        }
    }

    vector<point> res(0);
    i=N;
    do{
        res.push_back(a[i]);
        i=nxt[i];
    } while (i!=N);

    return res;
}
int main(){
    ifstream fin("infasuratoare.in");
    ofstream fout("infasuratoare.out");
    fin >> N;

    int i;
    for (i=1; i<=N; i++)
        fin >> a[i].x >> a[i].y;

    vector<point> ans(0);
    ans = gethull();
    fout << fixed << setprecision(9);

    fout << ans.size() << "\n";
    for (point P : ans)
        fout << P.x << " " << P.y << "\n";


    return 0;
}