Cod sursa(job #2054744)

Utilizator tgm000Tudor Mocioi tgm000 Data 2 noiembrie 2017 15:08:46
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include<cstdio>
#include<algorithm>
#define eps 1e-12
using namespace std;
struct punct{double x,y;};
punct v[120001];
int s[120001];
int comp(double a,double b){
    if(a+eps<b)
        return -1;
    else if(b+eps<a)
        return 1;
    else
        return 0;
}
bool cmp(punct a,punct b){
    if(comp(a.x,b.x)==-1)
        return true;
    else if(comp(a.x,b.x)==1)
        return false;
    else if(comp(a.y,b.y)==-1)
        return true;
    else
        return false;
}
double det(punct a,punct b,punct c){
    return a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-a.x*c.y-b.x*a.y;
}
int sgn(double a){
    return comp(a,0);
}
int main(){
    int n,i,top,topsol;
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%lf%lf",&v[i].x,&v[i].y);
    sort(v+1,v+n+1,cmp);
    s[1]=1;
    s[2]=2;
    top=2;
    for(i=3;i<=n;i++){
        while(top>1&&sgn(det(v[s[top-1]],v[s[top]],v[i]))<0&&sgn(det(v[s[top]],v[i],v[s[top-1]]))<0)
            top--;
        top++;
        s[top]=i;
    }
    topsol=top;
    top++;
    s[top]=n-1;
    for(i=n-2;i>=1;i--){
        while(top>topsol&&sgn(det(v[s[top-1]],v[s[top]],v[i]))<0&&sgn(det(v[s[top]],v[i],v[s[top-1]]))<0)
            top--;
        top++;
        s[top]=i;
    }
    printf("%d\n",top-1);
    for(i=1;i<top;i++)
        printf("%.6f %.6f\n",v[s[i]].x,v[s[i]].y);
    return 0;
}