Cod sursa(job #2150525)

Utilizator Constantin.Dragancea Constantin Constantin. Data 3 martie 2018 16:55:29
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>
using namespace std;

struct point{
    long double x, y;
} P[120010], sol[120010];

int n, s = 1, k;

bool crossproduct(point a, point b, point c){
    return (a.y - c.y)*(a.x - b.x) < (a.y - b.y)*(a.x - c.x);
}

int main(){
    ifstream cin ("infasuratoare.in");
    ofstream cout ("infasuratoare.out");
    cin >> n;
    for (int i=1; i<=n; i++){
        cin >> P[i].x >> P[i].y;
        if (P[i].x < P[s].x || (P[i].x == P[s].x && P[i].y < P[s].y)) s = i;
    }
    sol[++k] = P[s];
    int p;
    do{
        int j = (s+1)%n;
        for (int i=1; i<=n; i++){
            if (crossproduct(sol[k], P[j], P[i])) j = i;
        }
        p = j;
        sol[++k] = P[j];
    } while (p != s);
    cout << k-1 << "\n";
    for (int i=1; i<k; i++) cout << fixed << setprecision(12) << sol[i].x << " " << sol[i].y << "\n";
    return 0;
}