Cod sursa(job #1506397)

Utilizator tudormaximTudor Maxim tudormaxim Data 20 octombrie 2015 16:40:22
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 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 a.x*b.y + b.x*c.y + c.x*a.y - b.y*c.x - c.y*a.x - a.y*b.x;
}

inline bool cmp(point a, point b)
{
    return sarrus(v[1], a, b) > 0;
}

int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    int n, i, ind=1, st[nmax], top=0;
    scanf("%d", &n);
    for(i=1; i<=n; i++)
    {
        scanf("%lf %lf", &v[i].x, &v[i].y);
        if(v[i].x < v[ind].x) ind=i;
    }
    swap(v[1], v[ind]);
    sort(v+2, v+n+1, cmp);
    v[n+1]=v[1];
    st[++top]=1;
    for(i=2; i<=n; i++)
    {
        st[++top]=i;
        while( sarrus(v[st[top-1]], v[st[top]], v[i+1]) < 0) top--;
    }
    printf("%d\n", top);
    for(i=1; i<=top; i++)
        printf("%.6lf %.6lf\n", v[st[i]].x, v[st[i]].y);
    fclose(stdin);
    fclose(stdout);
    return 0;
}