Cod sursa(job #2262917)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 17 octombrie 2018 22:14:47
Problema Infasuratoare convexa Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
# include <fstream>
# include <algorithm>
# include <iomanip>
# include <cmath>
# define DIM 120010
# define INF 1000000010.0
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct{
    long double x,y;
};
punct v[DIM],s[DIM];
int n,i,u;
long double minx,miny;
long double dist(long double x1,long double y1,long double x2, long double y2){
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
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(punct a,punct b){
    if(det(0,0,a.x,a.y,b.x,b.y)==0)
        return dist(a.x,a.y,0,0)<dist(b.x,b.y,0,0);
    return det(0,0,a.x,a.y,b.x,b.y)>0;
}
int main () {
    fin>>n;
    minx=miny=INF;
    for(i=1;i<=n;i++){
        fin>>v[i].x>>v[i].y;
        minx=min(minx,v[i].x);
        miny=min(miny,v[i].y);
    }
    for(i=1;i<=n;i++){
        v[i].x-=minx;
        v[i].y-=miny;
    }
    sort(v+1,v+n+1,cmp);
    if(det(0,0,v[n-1].x,v[n-1].y,v[n].x,v[n].y)==0)
        swap(v[n],v[n-1]);
    s[1]=v[1];
    s[2]=v[2];
    u=2;
    for(i=3;i<=n;i++){
        while(det(s[u-1].x,s[u-1].y,s[u].x,s[u].y,v[i].x,v[i].y)<0&&u>=2)
            u--;
        s[++u]=v[i];
    }
    fout<<u<<"\n";
    for(i=1;i<=u;i++)
        fout<<setprecision(13)<<fixed<<s[i].x+minx<<" "<<s[i].y+miny<<"\n";
    return 0;
}