Cod sursa(job #1355348)

Utilizator daniel.grosuDaniel Grosu daniel.grosu Data 22 februarie 2015 17:04:00
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
using namespace std;

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

struct Point{
    double x;
    double y;
};

bool pointsort(Point A, Point B)
{
    return(A.x<B.x||(A.x==B.x && A.y<B.y));
}

double cross(Point O, Point A, Point B)
{
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

vector <Point> P;

int n;

int main() {
    fin>>n;
    for(int i=1; i<=n; ++i)
    {
        Point N;
        fin>>N.x>>N.y;
        P.push_back(N);
    }
    sort(P.begin(), P.end(), pointsort);
    int k=0;
    
    vector <Point> H(2*n);
    for(int i=0; i<n; ++i)
    {
        while(k>=2&&cross(H[k-2], H[k-1], P[i])<=0)k--;
            H[k++] = P[i];
    }
    for(int i=n-2, t=k+1; i>=0; i--) {
        while(k>=t && cross(H[k-2], H[k-1], P[i])<=0)k--;
            H[k++] = P[i];
    }
    fout<<--k<<"\n";
    fout << setprecision(6) << fixed;
    for(int i=1; i<k; ++i)
        fout<<H[i].x<<" "<<H[i].y<<"\n";
    
}