Cod sursa(job #1110326)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 17 februarie 2014 23:05:43
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

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

struct punct {
    double x;
    double y;
}v[120010];

int i, p,s[120010],n;

double cmp (punct a, punct b) {

    double ariec=a.x*b.y-b.x*a.y;
    if (ariec<0)
        return 0;
    else
        return 1;

}

int arie (int i, int j, int k) {

    double ariec = (v[j].x-v[i].x)*(v[k].y-v[i].y)-(v[k].x-v[i].x)*(v[j].y-v[i].y);
    if (ariec<0.000000000001)
        return 1;
    else
        return 0;

}

int main () {

    fin>>n;

    for (i=1;i<=n;i++)
        fin>>v[i].x>>v[i].y;


    sort (v+1,v+n+1,cmp);



    s[1]=1;
    s[2]=2;
    p=2;
    for (i=3;i<=n;i++) {
        while( arie (s[p-1],s[p],i) && p>=1 )
            p--;
        s[++p]=i;
    }
    fout<<p<<"\n";
    fout << setprecision(6) << fixed;
    for (i=1;i<=p;i++)
        fout<<v[s[i]].x<<" "<<v[s[i]].y<<"\n";

    return 0;
}