Cod sursa(job #2003628)

Utilizator VladTiberiuMihailescu Vlad Tiberiu VladTiberiu Data 23 iulie 2017 14:21:16
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <iomanip>
#include <cstring>
#include <fstream>

#define NMax 120005
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct conv{
    double x;double y;
}v[NMax],s[NMax];

int n,head;

double unghi(conv a, conv b, conv c){
    return (b.y - a.y) * (c.x - a.x) - (c.y - a.y) * (b.x - a.x);
}
bool cmp(conv a, conv b){
    return (unghi(v[1],a,b) > 0);
}
void citeste(){
    f >> n;
    for(int i = 1; i <= n; ++i)
        f >> v[i].x >> v[i].y;
}
void infasuratoare(){
    int poz = 1;
    for(int i = 1; i <= n; ++i)
        if(v[i].x < v[poz].x || (v[i].x == v[poz].x && v[i].y < v[poz].y))
            poz = i;
    swap(v[1],v[poz]);
    sort(v + 2, v + n + 1, cmp);

    s[1] = v[1];
    s[2] = v[2];
    head = 2;
    for(int i = 3; i <= n; ++i){
        while(head >= 2 && unghi(s[head - 1], s[head], v[i]) < 0)
            --head;
        s[++head] = v[i];
    }
}
void scrie(){
    g << head <<"\n";
    for(int i = head; i >= 1; --i){
        g <<fixed <<setprecision(6)<< s[i].x <<" "<< s[i].y <<"\n";
    }
}
int main()
{
    citeste();
    infasuratoare();
    scrie();
    return 0;
}