Cod sursa(job #2295254)

Utilizator Anastasia11Susciuc Anastasia Anastasia11 Data 3 decembrie 2018 14:01:35
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define Nmax 120005

using namespace std;

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

bool vis[Nmax];
int n;
int st[Nmax], top=2;
struct db{
double x, y;
}v[Nmax], X;

bool cmp(db a, db b)
{
    if(a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}

double pr(db a, db b, db c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

int main()
{
    f >> n;
    for (int i = 1; i <= n; i++)
    {
        f >> X.x >> X.y;
        v[i]=X;
    }
    sort(v+1, v+n+1, cmp);
    //g << v[1].x << " " << v[1].y;
    st[1]=1, st[2]=2; top=2;
    vis[2]=1;
    for (int i = 1; i <= n; i++)
    {
        if(vis[i] == 1) continue;
        while(top >= 2 && pr(v[st[top]], v[st[top-1]], v[i]) < 0)
            vis[st[top--]]=0;
        st[++top]=i;
        vis[i]=1;
    }
    for (int i = n; i >= 1; i--)
    {
        if(vis[i] == 1) continue;
        while(top >= 2 && pr(v[st[top]], v[st[top-1]], v[i]) < 0)
            vis[st[top--]]=0;
        st[++top]=i;
        vis[i]=1;
    }
    g << top-1 << '\n' << setprecision(6) << fixed;
    for (int i = 1; i < top; i++)
        g << v[st[i]].x << " " << v[st[i]].y << '\n';
    return 0;
}