Cod sursa(job #2521231)

Utilizator YetoAdrian Tonica Yeto Data 10 ianuarie 2020 16:13:08
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#define dim 120001
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct punct {
    double x, y;
};
punct v[dim], s[dim];
int n, i, j, pminim, k;

double arie (punct a, punct b, punct c) {
    return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
}
int cmp (punct a,punct b){
    punct c;
    c.x=0;
    c.y=0;
    if (arie (c,a,b))
        return arie (c,a,b)>0;
    return a.x*a.x+a.y*a.y > b.x*b.x+b.y*b.y;
}
int main () {
    fin>>n;
    pminim=0;
    v[0].x=1.0*1000000000;
    v[0].y=1.0*1000000000;
    for (i=1;i<=n;i++) {
        fin>>v[i].x>>v[i].y;
        if (v[i].y<v[pminim].y || (v[i].y==v[pminim].y && v[i].x<v[pminim].x))
            pminim=i;
    }
    v[0]=v[pminim];
    v[pminim]=v[1];
    v[1]=v[0];
    for (i=1;i<=n;i++){
        v[i].x-=v[0].x;
        v[i].y-=v[0].y;
    }
    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 (j=3;j<=n;j++){
        while (k>=2 && arie (s[k-1],s[k],v[j])<0)
            k--;
        s[++k]=v[j];
    }
    fout<<k<<"\n";
    for (i=1;i<=k;i++) {
        fout<<fixed<<setprecision(6)<<s[i].x+v[0].x<<" "<<s[i].y+v[0].y<<"\n";
    }
    return 0;
}