Cod sursa(job #2109493)

Utilizator emanuel_rRamneantu Emanuel emanuel_r Data 19 ianuarie 2018 19:59:03
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.92 kb
#include<bits/stdc++.h>

using namespace std;

struct trips
{
    double x, y;
    int idx;
    trips(double x, double y, double idx){
        this->x = x;
        this->y = y;
        this->idx = idx;
    }
    trips(){
        x = y = idx = 0;
    }
    bool operator<(trips other) const{
        if(x == other.x)
            return y < other.y;
        return x < other.x;
    }
};

vector <trips> G;
int t, n;
trips piv;
vector <trips> S;

void Read()
{
    scanf("%d", &n);
    double x, y;
    for(int i = 1; i <= n; i++){
        scanf("%lf %lf", &x, &y);
        G.push_back(*(new trips(x, y, i)));
    }
}

bool cmp(trips a, trips b)
{
    double da, db;
    da = (a.y - piv.y) / (a.x - piv.x);
    db = (b.y - piv.y) / (b.x- piv.x);
    if(abs(da - db) < 1E-14){
        return (a.x - piv.x) < (b.x - piv.x);
    }
    return da < db;
}

double CCW(trips a, trips b, trips p)
{
    return (p.y - a.y)*(b.x - a.x) - (p.x - a.x)*(b.y - a.y);
}

bool cmpid(trips a, trips b)
{
    return a.idx < b.idx;
}

void Solve()
{
    nth_element(G.begin(), G.begin(), G.end());
    piv = G.front();
    S.push_back(G.front());
    sort(G.begin() + 1, G.end(), cmp);

    S.push_back(G[1]);
    vector <trips>::iterator it;
    double ret;
    for(it = G.begin() + 2; it != G.end(); it++){
        ret = CCW(*(S.end() - 2), S.back(), *it);
        while(ret < 1E-14){
            S.pop_back();
            if(S.size() == 1)
                break;
            ret = CCW(*(S.end() - 2), S.back(), *it);
        }
        S.push_back(*it);
    }

    printf("%d\n", S.size());
    for(auto i : S)
        printf("%.6lf %.6lf\n", i.x, i.y);
    printf("\n");
}

void CleanUp()
{
    S.clear();
    G.clear();
}

int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    Read();
    Solve();
    CleanUp();
    return 0;
}