Cod sursa(job #2342889)

Utilizator Anastasia11Susciuc Anastasia Anastasia11 Data 13 februarie 2019 14:59:44
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define Nmax 120005

using namespace std;

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

double EPS=1e-12;
struct point{
double x, y;
}v[Nmax];
int n;
int st[2*Nmax], top;
double x, y;

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

double det(int a, int b, int c)
{
    double d=0;
    d+=v[a].x*v[b].y;
    d+=v[a].y*v[c].x;
    d+=v[b].x*v[c].y;
    d-=v[c].x*v[b].y;
    d-=v[c].y*v[a].x;
    d-=v[b].x*v[a].y;
    return d;
}

int main()
{
    f >> n;
    for (int i = 1; i <= n; i++)
    {
        f >> x >> y;
        v[i]={x, y};
    }

    sort(v+1, v+n+1, cmp);

    //for (int i = 1; i <= n; i++) cout << v[i].x << " " << v[i].y << '\n';

    st[1]=1, st[2]=2;
    top=2;
    for (int i = 3; i <= n; i++)
    {
        while(top>1 && det(st[top], st[top-1], i)<EPS) top--;
        top++;
        st[top]=i;
    }

    for (int i = n-1; i > 1; i--)
    {
        while(top>1 && det(st[top], st[top-1], i)<EPS) top--;
        top++;
        st[top]=i;
    }
    //cout << fixed << setprecision(10) << EPS;
    top--;
    g << top << '\n';
    for (int i = 1; i <= top; i++)
        g << fixed << setprecision(6) << v[st[i]].x << " " << fixed << setprecision(6) << v[st[i]].y << '\n';

    return 0;
}