Cod sursa(job #2569674)

Utilizator AndreeaGherghescuAndreea Gherghescu AndreeaGherghescu Data 4 martie 2020 13:09:04
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <algorithm>
#include<iomanip>
#define inf 1e8

using namespace std;

ifstream in ("infasuratoare.in");
ofstream out ("infasuratoare.out");

const int N=120001;
struct punct
{
    long double x,y,panta;
}v[N+1];
deque <int> stv;

bool comp (punct a, punct b)
{
    return a.panta<b.panta;
}
bool col (punct a, punct b, punct c)
{
    return (a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x) >= 0;
}
int main()
{
    int n;
    int ind=1;
    in>>n;
    for (int i=1;i<=n;i++)
    {
        in>>v[i].x>>v[i].y;
        if (v[i].x<v[ind].x || (v[i].x==v[ind].x && v[i].y<v[ind].y))
            ind=i;
    }
    swap (v[1],v[ind]);
    for (int i=2;i<=n;i++)
    {
        if (v[i].x==v[1].x) v[i].panta=inf;
        else v[i].panta=(v[i].y-v[1].y)/(v[i].x-v[1].x);
    }
    sort (v+2,v+n+1,comp);
    stv.push_back(1);
    stv.push_back(2);
    v[n+1]=v[1];
    int i=3;
    while (i<=n+1 && stv.front()!=stv.back())
    {
        while (stv.size()>=2 && !col(v[stv[stv.size()-2]],v[stv[stv.size()-1]],v[i]))
            stv.pop_back();
        stv.push_back(i++);
    }
    out<<stv.size()-1<<'\n';
    out<<fixed<<setprecision(6);
    for (i=0;i<stv.size()-1;i++)
        out<<v[stv[i]].x<<' '<<v[stv[i]].y<<'\n';
    return 0;
}