Cod sursa(job #2166175)

Utilizator SolcanMihaiSolcan Mihai Andrei SolcanMihai Data 13 martie 2018 15:54:41
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.95 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#include <algorithm>

using namespace std;

const double pi = 3.141592654;

struct Punct{
    double x, y;
    double unghi;

    Punct(){
        unghi = 0;
    }
};

double minx, miny;

int n;
Punct puncte[120005];
vector<Punct> Q;

bool cmp(Punct x, Punct y){
    if(x.unghi < y.unghi){
        return true;
    }
    else{
        return false;
    }
}

void citire(){
    scanf("%d\n", &n);

    minx = miny = 10000000000;

    double x, y;

    for(int i = 0; i < n; i++){
        scanf("%lf %lf", &x, &y);
        puncte[i].x = x;
        puncte[i].y = y;

        if(x < minx){
            minx = x;
            miny = y;
        }
        else if(x == minx && y < miny){
            miny = y;
        }
    }

    for(int i = 0; i < n; i++){
        if(puncte[i].x == minx && puncte[i].y == miny){
            puncte[i].unghi = -10;
            continue;
        }
        else{
            puncte[i].unghi = atan2(puncte[i].y - miny, puncte[i].x - minx);
        }
    }

    sort(puncte, puncte + n, cmp);
}

double det(Punct x, Punct y, Punct z){
    return (y.x - x.x) * (z.y - x.y) - (z.x - x.x) * (y.y - x.y);
}

void addToStack(int ind){
    Punct x, y, z;
    z = puncte[ind];
    y = Q.back();
    x = Q[Q.size() - 2];

    while(det(x, y, z) < 0 && Q.size() > 1){
        Q.pop_back();
        y = Q.back();
        x = Q[Q.size() - 2];
    }

    Q.push_back(z);
}

void solve(){
    Q.push_back(puncte[0]);
    Q.push_back(puncte[1]);

    for(int i = 2; i < n; i++){
        addToStack(i);
    }

    printf("%d\n", Q.size());

    int l = Q.size();

    for(int i = 0; i < l; i++){
        printf("%lf %lf\n", Q[i].x, Q[i].y);
    }
}

int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);

    citire();
    solve();

    return 0;
}