Cod sursa(job #2150545)

Utilizator Constantin.Dragancea Constantin Constantin. Data 3 martie 2018 17:09:06
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>
using namespace std;

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

int n, s = 1, k = 2;

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);
}

bool cmp(point a, point b){
    return !crossproduct(a, b, P[1]);
}

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;
    }
    swap(P[1], P[s]);
    sort(P+2, P+1+n, cmp);
    sol[1] = P[1];
    sol[2] = P[2];
    for (int i=3; i<=n; i++){
        while (k >= 2 && crossproduct(sol[k-1], sol[k], P[i])) k--;
        sol[++k] = P[i];
    }
    cout << k << "\n";
    for (int i=1; i<=k; i++) cout << fixed << setprecision(12) << sol[i].x << " " << sol[i].y << "\n";
    return 0;
}