Cod sursa(job #2196700)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 20 aprilie 2018 09:59:48
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
# include <fstream>
# include <algorithm>
# include <cmath>
# include <iomanip>
# define DIM 120010
# define x first
# define y second
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
pair<long double,long double> v[DIM],sol[DIM],df;
int n,u,i;
long double dist(pair<long double,long double> a){
    return sqrt(a.x*a.x+a.y*a.y);
}
long double det(long double x1,long double Y1,long double x2,long double y2,long double x3,long double y3){
    return (x2-x1)*(y3-Y1)-(x3-x1)*(y2-Y1);
}
bool cmp(pair<long double,long double> a,pair<long double,long double> b){
    if(det(0,0,a.x,a.y,b.x,b.y)==0)
        return dist(a)<dist(b);
    return det(0,0,a.x,a.y,b.x,b.y)<0;
}
int main () {
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i].x>>v[i].y;
    sort(v+1,v+n+1);
    df=v[1];
    for(i=n;i>=1;i--){
        v[i].x-=v[1].x;
        v[i].y-=v[1].y;
    }
    sort(v+2,v+n+1,cmp);
    sol[++u]=v[1];
    sol[++u]=v[2];
    for(i=3;i<=n;i++){
        while(det(sol[u-1].x,sol[u-1].y,sol[u].x,sol[u].y,v[i].x,v[i].y)>=0&&u>1)
            u--;
        sol[++u]=v[i];
    }
    fout<<u<<"\n";
    for(i=u;i>=1;i--)
        fout<<setprecision(6)<<fixed<<sol[i].x+df.x<<" "<<sol[i].y+df.y<<"\n";
    return 0;
}