Cod sursa(job #2521221)

Utilizator YetoAdrian Tonica Yeto Data 10 ianuarie 2020 16:02:07
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
int n, i, j, k, pminim;
struct punct {
    double first, second;
};
punct v[120001], s[120001];
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
double arie (punct a, punct b, punct c) {
    return (b.first-a.first)*(c.second-a.second) - (c.first-a.first)*(b.second-a.second);
}
int cmp (punct a, punct b)
{
    punct c;
    c.first=0;
    c.second=0;
    int d=arie(c, a, b);
    if (d)
        return d>0;
    else
        return a.first*a.first+a.second*a.second > b.first*b.first+b.second*b.second;
}
int main () {
    fin>>n;
    pminim=0;
    v[0].first=1.0*1000000000;
    v[0].second=1.0*1000000000;
    for (i=1;i<=n;i++) {
        fin>>v[i].first>>v[i].second;
        if ((v[i].second<v[pminim].second) || (v[i].second==v[pminim].second && v[i].first<v[pminim].first))
            pminim=i;
    }
    v[0]=v[pminim];
    v[pminim]=v[1];
    v[1]=v[0];
    for (i=1;i<=n;i++) {
        v[i].first-=v[0].first;
        v[i].second-=v[0].second;
    }
    sort(v+2, v+n+1, cmp);
    for (j=3;j<=n;j++) {
        if (arie(v[j], v[1], v[2]))
            break;
    }
    i=2;
    j--;
    while (i<j) {
        swap(v[i], v[j]);
        i++;
        j--;
    }
    s[1]=v[1];
    s[2]=v[2];
    k=2;
    for (i=3;i<=n;i++) {
        while (k>=2 && arie(s[k-1], s[k], v[i])<0)
            k--;
        s[++k]=v[i];
    }
    fout<<k<<"\n";
    for (i=1;i<=k;i++) {
        fout<<fixed<<setprecision(6)<<s[i].first+v[0].first<<" "<<s[i].second+v[0].second<<"\n";
    }
    return 0;
}