Cod sursa(job #1500583)

Utilizator tudormaximTudor Maxim tudormaxim Data 12 octombrie 2015 10:44:36
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>
using namespace std;
const int nmax = 120005;
struct point {double x, y;} v[nmax], st[nmax];


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

inline int cmp(point a, point b)
{
    return det(v[1], a, b) < 0;
}
int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    int i, n, top=0;
    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);
    st[++top]=v[1];
    st[++top]=v[2];
    for(i=3; i<=n; i++)
    {
        while(top>=2 && det(st[top-1], st[top], v[i])>0) --top;
        st[++top]=v[i];
    }
    printf("%d\n", top);
    while(top>0)
    {
        printf("%.6lf %.6lf\n", st[top].x, st[top].y);
        top--;
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}