Cod sursa(job #1051243)

Utilizator Aleks10FMI - Petrache Alex Aleks10 Data 9 decembrie 2013 21:04:36
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>

#define MAX_N 120001
using namespace std;

typedef pair<double, double> punct;

punct v[MAX_N];
punct stiva[MAX_N];
int n,head;

double prod(const punct& a, const punct& b, const punct& c){
    return (b.first-a.first)*(c.second-a.second)-(b.second-a.second)*(c.first-a.first);
}

int cmp(const punct& p1, const punct& p2){
    return prod(v[1],p1,p2)<0;
}

int main()
{
    int i;
    ifstream f("infasuratoare.in");
    ofstream g("infasuratoare.out");
    f>>n;
    for(i=1;i<=n;i++){
        f>>v[i].first>>v[i].second;
    }

    //sorteaza puncte
    int pos=1;
    for(i=2;i<=n;i++)
        if(v[i]<v[pos])
            pos=i;
    swap(v[1],v[pos]);
    sort(v+2,v+n+1,cmp);

    /*for(i=1;i<=n;i++){
        cout<<v[i].first<<" "<<v[i].second<<'\n';
    }*/

    stiva[1]=v[1];
    stiva[2]=v[2];
    head=2;
    for(i=3;i<=n;i++){
        while(head>=2 && prod(stiva[head-1],stiva[head],v[i])>0)
            head--;
        stiva[++head]=v[i];
    }

    g<<fixed;
    g<<head<<'\n';
    for(i=head;i>=1;i--)
        g<<setprecision(12)<<stiva[i].first<<" "<<stiva[i].second<<'\n';
    return 0;
}