Cod sursa(job #2351082)

Utilizator mihaigrozaGroza Mihai mihaigroza Data 21 februarie 2019 22:45:43
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <fstream>
#include <iomanip>

using namespace std;

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

#define x first
#define y second

typedef pair<double, double> puncte;

int n,head;
puncte v[120005];
puncte stack[120005];

void citire()
{
    f>>n;
    for(int i=1;i<=n;i++)
       f>>v[i].x>>v[i].y;
}
double formula(puncte & a,puncte& b,puncte& c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int cmp(puncte& p1,puncte& p2)
{
    return formula(v[1], p1, p2) < 0;
}
void sortare()
{
    int pos=1;
    for(int i=2;i<=n;++i)
        if(v[i]<v[pos])
            pos=i;
    swap(v[1],v[pos]);
    sort(v+2,v+n+1,cmp);
}
void best()
{
    sortare();
    stack[1]=v[1];
    stack[2]=v[2];
    head=2;
    for(int i=3;i<=n;++i)
    {
        while(head>=2 && formula(stack[head-1],stack[head],v[i])>0)
            head--;
        stack[++head]=v[i];
    }
}
void afisare()
{
    g<<fixed;
    g<<head<<"\n";
    for(int i=head;i>=1;i--)
        g<<setprecision(9)<<stack[i].x<<" "<<stack[i].y<<endl;
}
int main()
{
    citire();
    best();
    afisare();
}