Cod sursa(job #2391437)

Utilizator Constantin.Dragancea Constantin Constantin. Data 28 martie 2019 20:53:52
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>
using namespace std;

#define N 120005
#define eps 0.000001
struct point{
    double x, y;
} a[N], p[N];
int n, s = 1;

// 1 - la stanga, 0 - la dreapta
bool det(point a, point b, point c){
    double rs = a.x * b.y + b.x * c.y + c.x * a.y;
    rs -= (b.y * c.x + c.y*a.x + a.y * b.x);
    return (rs > eps);
}

bool cmp (point unu, point doi){
    return det(a[1], unu, doi);
}

int main(){
    ifstream cin ("infasuratoare.in");
    ofstream cout ("infasuratoare.out");
    cin >> n;
    for (int i=1; i<=n; i++){
        cin >> a[i].x >> a[i].y;
        if (a[i].x < a[s].x || (a[i].x == a[s].x && a[i].y < a[s].y)) s = i;
    }
    swap(a[1], a[s]);
    sort(a+2, a+1+n, cmp);
    p[1] = a[1]; p[2] = a[2]; p[3] = a[3]; s = 3;
    for (int i=4; i<=n; i++){
        while (s > 2 && !det(p[s-1], p[s], a[i])) s--;
        p[++s] = a[i];
    }
    cout << s << '\n';
    cout << fixed << setprecision(6);
    for (int i=1; i<=s; i++) cout << p[i].x << ' ' << p[i].y << '\n';
    return 0;
}