Cod sursa(job #2205901)

Utilizator Constantin.Dragancea Constantin Constantin. Data 20 mai 2018 16:05:08
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>
using namespace std;

int n,s = 1, k = 2;
struct point{
    double x, y;
} p[120010], ans[120010];

bool det(point a, point b, point c){
    return (a.x*b.y + b.x*c.y + c.x*a.y - c.x*b.y - c.y*a.x - a.y*b.x > 0);
}

bool cmp(point a, point b){
    return det(p[1], a, b);
}

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);
    ans[1] = p[1]; ans[2] = p[2];
    for (int i=3; i<=n; i++){
        while (!det(ans[k-1], ans[k], p[i])) k--;
        ans[++k] = p[i];
    }
    cout << k << "\n" << fixed << setprecision(12);
    for (int i=1; i<=k; i++) cout << ans[i].x << " " << ans[i].y << "\n";
    return 0;
}