Cod sursa(job #1882518)

Utilizator VladTiberiuMihailescu Vlad Tiberiu VladTiberiu Data 17 februarie 2017 11:48:24
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

const int NMax = 120003;
const int INF = 0x3f3f3f3f;

struct stat{
    double x,y;
};

stat a[NMax];
double mnx;
int s[NMax];
int n,mnxind,top;

double unghi(stat A, stat B, stat C){
    return (A.y - B.y) * (A.x - C.x) - (A.y - C.y) * (A.x - B.x);
}
bool cmp(stat x, stat y){
    return (unghi(a[1],x,y) > 0);
}

int main()
{
    f >> n;
    double mnx = INF;
    for(int i = 1; i <= n; ++i){
        f >> a[i].x >> a[i].y;
        if(a[i].x < mnx){
            mnx = a[i].x;
            mnxind = i;
        }
    }
    swap(a[mnxind],a[1]);
    sort(a + 2, a + n + 1, cmp);

    s[++top] = 1;
    s[++top] = 2;
    for(int i = 3; i <= n; ++i){
        while(unghi(a[s[top - 1]], a[s[top]], a[i]) < 0){
            top--;
        }
        s[++top] = i;
    }
    g << top << '\n';
    for(int i = top; i >= 1; --i){
        g << fixed << setprecision(6) << a[s[i]].x << ' ' << a[s[i]].y << '\n';
    }
    return 0;
}