Cod sursa(job #2403146)

Utilizator alex2209alexPavel Alexandru alex2209alex Data 11 aprilie 2019 12:04:44
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
//-------------------------------
//Variabile globale
int n,rasp;
struct str
{
    double x,y;
}v[120001],v2[120001];
//-------------------------------
//Functii
void citire();
void sortare();
bool comparare(str,str);
double comparare2(str,str,str);
void infasuratoare();
void afisare();
//-------------------------------
int main()
{
    citire();
    sortare();
    infasuratoare();
    afisare();
    return 0;
}
//-------------------------------
void citire()
{
    f >> n;
    for(int i = 1;i <= n;++i)
        f >> v[i].x >> v[i].y;
}
//-------------------------------
void sortare()
{
    int pos = 1;
    for(int i = 2; i <= n; ++i)
        if(v[i].x < v[pos].x or (v[i].x == v[pos].x && v[i].y < v[pos].y))
            pos = i;
    swap(v[1], v[pos]);
    sort(v + 2, v + n + 1, comparare);
}
//-------------------------------
bool comparare(str a,str b)
{
    return comparare2(v[1],a,b) < 0;
}
//-------------------------------
double comparare2(str a,str b,str c)
{
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
//-------------------------------
void infasuratoare()
{
    v2[1] = v[1];
    v2[2] = v[2];
    rasp = 2;
    for(int i = 3;i <= n;++i)
    {
        while(rasp >= 2 && comparare2(v2[rasp - 1],v2[rasp],v[i]) > 0)
            rasp--;
        rasp++;
        v2[rasp]=v[i];
    }
}
//-------------------------------
void afisare()
{
    g << rasp << '\n';
    for(int i = rasp;i >= 1;--i)
        g << fixed << setprecision(12) << v2[i].x << " " << v2[i].y << '\n';
}