Cod sursa(job #2108620)

Utilizator emanuel_rRamneantu Emanuel emanuel_r Data 18 ianuarie 2018 17:01:03
Problema Infasuratoare convexa Scor 20
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(int x, int y, int 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-10){
        return (a.x - piv.x) < (b.x - piv.x);
    }
    return da < db;
}

double CCW(trips p1, trips p2, trips p3)
{
    return (p1.x*p2.y + p2.x*p3.y + p1.y*p3.x)  -  (p3.x*p2.y + p1.x*p3.y + p1.y*p2.x);
}

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());
    G.erase(G.begin());
    sort(G.begin(), G.end(), cmp);
    S.push_back(G[0]);
    vector <trips>::iterator it;
    double ret;
    for(it = G.begin() + 1; it != G.end(); it++){
        ret = CCW(*(S.end() - 2), S.back(), *it);
        while(ret <= 1E-10 and S.size() > 1){
            S.pop_back();
            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;
}