Cod sursa(job #1980686)

Utilizator gabib97Gabriel Boroghina gabib97 Data 13 mai 2017 20:26:22
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <bits/stdc++.h>

#define N 120005
using namespace std;
int n, S[N], u;
const double inf = numeric_limits<double>::max();

struct point {
    double x, y;
} p[N];

double det(point p0, point p1, point p2)
{
    return ((p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y));
}

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

bool cmp(point a, point b)
{
    double d = det(p[1], a, b);
    return (d > 0 || (d == 0 && dist(p[1], a) < dist(p[1], b)));
}

void solve()
{
    int i;
    double d;
    u = 0;
    S[++u] = 1;
    S[++u] = 2;

    for (i = 3; i <= n; i++) {
        d = det(p[S[u - 1]], p[S[u]], p[i]);

        if (d > 0)
            S[++u] = i;
        else if (d == 0) S[u] = i;
        else {
            while (d < 0) {
                u--;
                d = det(p[S[u - 1]], p[S[u]], p[i]);
            }
            S[++u] = i;
        }
    }
}

int main()
{
    int i;
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    scanf("%i", &n);

    int q = 1;
    double mx = inf, my = inf;
    for (i = 1; i <= n; i++) {
        scanf("%lf%lf", &p[i].x, &p[i].y);
        if (p[i].y < my || (p[i].y == my && p[i].x < mx)) {
            my = p[i].y;
            mx = p[i].x;
            q = i;
        }
    }

    swap(p[1], p[q]);
    sort(p + 2, p + n + 1, cmp);

    solve();

    printf("%i\n", u);
    for (i = 1; i <= u; i++)
        printf("%lf %lf\n", p[S[i]].x, p[S[i]].y);

    return 0;
}