Cod sursa(job #2019677)

Utilizator victoreVictor Popa victore Data 8 septembrie 2017 12:21:30
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>

#define pb(x) push_back(x)
#define x first
#define y second

using namespace std;

const int nmax=120005;
const double inf=2e9;
const double eps=1e-12;

typedef pair<double,double> dd;

dd punct[nmax];

int n,top;

inline double dist(dd p1,dd p2)
{
    return sqrt((p1.x - p2.x)*(p1.x-p2.x) + (p1.y - p2.y)*(p1.y-p2.y));
}

inline double cp(dd p1,dd p2,dd p3)
{
    return (p2.x-p1.x)*(p3.y-p2.y) - (p2.y-p1.y)*(p3.x-p2.x);
}

inline int ccw(dd p1,dd p2,dd p3)
{
    double a=cp(p1,p2,p3);
    if(a >= eps)
        return 1;
    if(a <= -eps)
        return -1;
    return 0;
}

inline bool cmp(const dd &p1, const dd &p2)
{
    double c1=ccw(punct[1],p1,p2);
    if(c1 == 1)
        return 1;
    if(c1 == 0)
        return dist(punct[0],p1) - dist(punct[0],p2) < eps;
    return 0;
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int i,j;
    int ll=1;
    scanf("%d",&n);
    for(i=1;i<=n;++i)
    {
        scanf("%lf %lf",&punct[i].x,&punct[i].y);
        if(punct[i].y -punct[ll].y <=-eps || (fabs(punct[i].y - punct[ll].y) < eps && punct[i].x - punct[ll].x <= -eps))
            ll=i;
    }
    double aux=punct[1].x;
    punct[1].x = punct[ll].x;
    punct[ll].x = aux;
    aux=punct[1].y;
    punct[1].y = punct[ll].y;
    punct[ll].y = aux;
    sort(punct+2,punct+n+1,cmp);
    vector<int> st(n+5);
    st[0] = 1;
    st[1] = 2;
    punct[n+1]=punct[1];
    top=1;
    i=3;
    while(i<=n+1)
    {
        if(ccw(punct[st[top-1]] , punct[st[top]] , punct[i]) > 0)
        {
            st[++top]=i;
            ++i;
        }
        else
            --top;
    }
    printf("%d\n",(top));
    for(i=0;i<top;++i)
    {
        printf("%lf %lf\n",punct[st[i]].x,punct[st[i]].y);
    }
}