Cod sursa(job #1535720)

Utilizator timicsIoana Tamas timics Data 25 noiembrie 2015 03:43:22
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include<iostream>
#include<vector>
#define pb push_back
using namespace std;
int N;
double X,Y;

struct pt {
    double x, y; 
};

vector<pt> a;

bool cmp (pt a, pt b) {
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}

bool cw (pt a, pt b, pt c) {
    return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) < 0;
}

bool ccw (pt a, pt b, pt c) {
    return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) > 0;
}

void convex_hull (vector<pt> & a) {
    if (a.size() == 1)  return;
    sort (a.begin(), a.end(), &cmp);
    pt p1 = a[0],  p2 = a.back();
    vector<pt> up, down;
    up.push_back (p1);
    down.push_back (p1);
    for (size_t i=1; i<a.size(); ++i) {
        if (i==a.size()-1 || cw (p1, a[i], p2)) {
            while (up.size()>=2 && !cw (up[up.size()-2], up[up.size()-1], a[i]))
                up.pop_back();
            up.push_back (a[i]);
        }
        if (i==a.size()-1 || ccw (p1, a[i], p2)) {
            while (down.size()>=2 && !ccw (down[down.size()-2], down[down.size()-1], a[i]))
                down.pop_back();
            down.push_back (a[i]);
        }
    }
    a.clear();
    for (size_t i=0; i<up.size(); ++i)
        a.push_back (up[i]);
    for (size_t i=down.size()-2; i>0; --i)
        a.push_back (down[i]);
}

int main() {
    //freopen("input.in","r",stdin);
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&N);
    for(int i=1;i<=N;++i) {
        scanf("%lf%lf",&X,&Y);
        pt p;
        p.x = X;
        p.y = Y;
        a.pb(p);
    }
    convex_hull(a);
    cout<<a.size()<<"\n";
    for(int i=a.size()-1;i>=0;--i) {
        printf("%.12lf %.12lf\n",a[i].x,a[i].y);
    }
}