Cod sursa(job #1318569)

Utilizator retrogradLucian Bicsi retrograd Data 16 ianuarie 2015 09:41:47
Problema Infasuratoare convexa Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#include<fstream>
#include<vector>
#include<algorithm>
#include<iomanip>
#define INF 9999999

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

typedef long double var;
struct Punct {
    var x, y;
    Punct(var a, var b) {
        x = a; y = b;
    }
    const bool operator==(const Punct p) const {
        return (x == p.x)&&(y == p.y);
    }
};


var xmin = INF, ymin = INF;
Punct start(0, 0);

inline var angle(Punct p, Punct q) {
    if(p.x == q.x) {
        if(p.y < q.y) return -INF;
        if(p.y == q.y) return INF+1;
        return INF;
    }
   return (q.y-p.y) / (q.x-p.x);
}

inline bool cmp(const Punct &a, const Punct &b) {
    if(a == start) return 1;
    if(b == start) return 0;
    if(a.x == start.x) return 1;
    if(b.x == start.x) return 0;

    return (a.y - start.y) * (b.x - start.x) > (a.x - start.x)*(b.y - start.y);
}

vector<Punct> SOL;
vector<Punct> PUNCTE;


int main() {
    var x, y;
    int n, i;
    fin>>n;

    for(i=1; i<=n; i++) {
        fin>>x>>y;
        PUNCTE.push_back(Punct(x, y));
        if(x<xmin || x==xmin && y<ymin) {
            start = PUNCTE[PUNCTE.size() - 1];
            xmin = start.x;
            ymin = start.y;
        }
    }
    sort(PUNCTE.begin(), PUNCTE.end(), cmp);
    SOL.push_back(PUNCTE[0]);
    SOL.push_back(PUNCTE[1]);
    int size = 1;
    for(i=2; i<n; i++) {
        while((SOL[size].x-SOL[size-1].x)*(PUNCTE[i].y-SOL[size].y) > (SOL[size].y - SOL[size-1].y) * (PUNCTE[i].x - SOL[size].x)) {
            SOL.pop_back();
            size --;
        }
        SOL.push_back(PUNCTE[i]);
        size ++;
    }
    fout<<size+1<<'\n';
    for(int i = size;i>=0; i--) {
        fout<<setprecision(30)<<SOL[i].x;
        fout<<" ";
        fout<<setprecision(30)<<SOL[i].y<<'\n';
    }

    return 0;
}