Cod sursa(job #1500671)

Utilizator tudormaximTudor Maxim tudormaxim Data 12 octombrie 2015 16:02:38
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>
using namespace std;

const int nmax = 120005;
struct point {double x, y;} v[nmax];

inline double sarrus(point a, point b, point c)
{
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}

inline bool cmp(point a, point b)
{
    if(a.x == b.x) return a.y < b.y;
    return  a.x < b.x;
}

int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    int n, i, top=0, st[nmax], p=1;
    bool viz[nmax];
    scanf("%d", &n);
    for(i=1; i<=n; i++)
    {
        scanf("%lf %lf", &v[i].x, &v[i].y);
        viz[i]=false;
    }
    sort(v+1, v+n+1, cmp);
    st[++top]=1, st[++top]=2, viz[2]=true;
    for(i=1; i; i=i+p)
    {
        if (viz[i]==false)
        {
            while(top > 1 && sarrus(v[st[top-1]], v[st[top]], v[i])>=0)
                viz[st[top--]]=false;
            st[++top]=i;
            viz[i]=true;
        }
        if(i==n) p=-p;
    }

    printf("%d\n", --top);
    while(top)
    {
        printf("%.6lf %.6lf\n", v[st[top]].x, v[st[top]].y);
        top--;
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}