Cod sursa(job #1409494)

Utilizator 4ONI2015oni2015 4ONI2015 Data 30 martie 2015 15:55:47
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>
#define N 120005
#define punct pair<double, double>
#define x first
#define y second

using namespace std;
punct p[N], q[N];
int cnt, n, i, mini;
double cp(punct a, punct b, punct c)
{
    return a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - b.y * c.x - c.y * a.x;
}
bool crit(punct a, punct b)
{
    return cp(p[1], a, b) < 0.0;
}
int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    scanf("%d", &n);
    mini = 1;
    for(i = 1; i <= n; i++)
    {
        scanf("%lf%lf", &p[i].x, &p[i].y);
        if(p[i] < p[mini])
            mini = i;
    }
    swap(p[1], p[mini]);
    sort(p + 2, p + n + 1, crit);
    for(i = 1; i <= n; i++)
    {
        while(cnt > 1 && cp(q[cnt - 1], q[cnt], p[i]) > 0)cnt--;
        q[++cnt] = p[i];
    }
    printf("%d\n", cnt);
    for(; cnt; cnt--)
        printf("%.12lf %.12lf\n", q[cnt].x, q[cnt].y);
    return 0;
}