Cod sursa(job #2310909)

Utilizator bogdi1bogdan bancuta bogdi1 Data 2 ianuarie 2019 13:11:45
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.24 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const double eps = 1.e-12;
struct Points
{
    double x,y;
};
Points v[120005];
Points sol[120005];
int st[120005];
double det(Points P1, Points P2, Points P3)
{
    return (P2.x-P1.x)*(P3.y-P1.y)-(P2.y-P1.y)*(P3.x-P1.x);
}
bool cmp1(Points P1, Points P2)
{
    if(fabs(P1.x-P2.x)<eps)
        return P1.y-P2.y<eps;
    return P1.x-P2.x<eps;
}
bool cmp2(Points P1, Points P2)
{
    if(fabs(P1.x-P2.x)<eps)
        return P1.y-P2.y>eps;
    return P1.x-P2.x<eps;
}
int main()
{   freopen("infasuratoare.in", "r",stdin);
    freopen("infasuratoare.out", "w",stdout);
    int n,i,top,nr,ok=0,ii,minx=2000000000,miny=2000000000;
    scanf("%d", &n);
    for(i=1; i<=n; i++)
        scanf("%lf%lf", &v[i].x, &v[i].y);
    sort(v+1, v+n+1,cmp1);
    st[1]=1;
    st[2]=2;
    top=2;
    double x=det(v[1], v[2], v[3]);
    for(i=3; i<=n; i++){
        while(top>=2 && det(v[st[top-1]], v[st[top]], v[i])<eps)
            top--;
        st[++top]=i;
    }
    for(i=1; i<=top; i++)
        sol[i]=v[st[i]];
    nr=top;
    sort(v+1, v+n+1,cmp2);
    st[1]=1;
    st[2]=2;
    top=2;
    for(i=3; i<=n; i++){
        while(top>=2 && det(v[st[top-1]], v[st[top]], v[i])>eps)
            top--;
        st[++top]=i;
    }
    reverse(st+1, st+top+1);
    if(fabs(v[n].x-v[n-1].x)<eps)
        ok=2;
    if(v[2].x-v[1].x>eps)
        ok++;
    if(v[n].x-v[n-1].x>eps)
        ok++;
    printf("%d\n", nr+top-ok);
    for(i=1; i<=nr; i++){
        if(sol[i].y<miny){
            miny=sol[i].y;
            minx=sol[i].x;
            ii=i;
        }
        else
            if(sol[i].y==miny){
                if(sol[i].x<minx){
                    minx=sol[i].x;
                    ii=i;
                }
            }
    }
    for(i=ii; i<=nr; i++)
        printf("%lf %lf\n", sol[i].x, sol[i].y);
    i=1;
    if(fabs(v[n].x-v[n-1].x)<eps)
        i+=2;
    else
        i++;
    for(; i<top; i++)
        printf("%lf %lf\n", v[st[i]].x, v[st[i]].y);
    if(fabs(v[2].x-v[1].x)<eps)
        printf("%lf %lf\n", v[st[i]].x, v[st[i]].y);
    for(i=1; i<ii; i++)
        printf("%lf %lf\n", sol[i].x, sol[i].y);
    return 0;
}