Cod sursa(job #2158380)

Utilizator ASTELOTudor Enescu ASTELO Data 10 martie 2018 12:28:33
Problema Infasuratoare convexa Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;

struct pct{
    double x, y, p;
} v[120001];

bool sortare (pct a, pct b){
    if (a.y == b.y)
        return a.x < b.x;
    return a.y < b.y;
}

int arie (int i, int j, int l)
{
    int a = v[i].x * v[j].y - v[j].y * v[l].x + v[j].x * v[l].y
        - v[l].y * v[i].x + v[l].x * v[i].y - v[i].y * v[j].x;
    if (a < 0)
        return -1;
    if (a > 0)
        return 1;
    return 0;
}

int n, w[120001];

int main ()
{
    ifstream in("infasuratoare.in");
    ofstream out("infasuratoare.out");

    int l;
    in >> n;

    for (int i=1; i<=n; i++){
        in >> v[i].x >> v[i].y;
    }

    sort (v+1, v+n+1, sortare);

    w[1] = 1;
    l = 1;

    for (int i=2; i<n; i++){
        v[i].p = arie (1, n, i);
        if (v[i].p < 0){
            if (l == 1){
                l++;
                w[l] = i;
            }
            else{
                while(arie (w[l], w[l-1], i) >= 0 ){
                    l --;
                }
                l ++;
                w[l] = i;
            }
        }
    }

    l++;
    w[l] = n;
    for (int i=n-1; i>1; i--){
        if (v[i].p > 0){
            if (w[l] == n){
                l ++;
                w[l] = i;
            }
            else{
                while(arie (w[l], w[l-1], i) >= 0 ){
                    l --;
                }
                l ++;
                w[l] = i;
            }
        }
    }

    out << l << endl;

    for (int i=1; i<=l; i++){
        out << setprecision(6) << v[w[i]].x << " " << setprecision(6) << v[w[i]].y << endl;
    }

    /*for (int i=1; i<=n; i++){
        out << v[i].x << " " << v[i].y << endl;
    }*/

    return 0;
}