Cod sursa(job #2870970)

Utilizator popoviciAna16Popovici Ana popoviciAna16 Data 12 martie 2022 19:04:44
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;

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

struct punct
{
    long double x, y;
} p[120001];

inline long double det (punct a, punct b, punct c)
{
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}

bool comp (punct a, punct b)
{
    return det (p[1], a, b) > 0;
}

int s[120001];

int main()
{
    int n, i, ind = 1;
    fin >> n;
    for (i = 1; i<=n; i++)
    {
        fin >> p[i].x >> p[i].y;
        if (p[i].y < p[ind].y || (p[i].y == p[ind].y && p[i].x < p[ind].x))
            ind = i;
    }
    swap (p[1], p[ind]);
    sort (p+2, p+n+1, comp);

    s[0] = 2;
    s[1] = 1;
    s[2] = 2;
    for (i = 3; i<=n; i++)
    {
        while (s[0] >= 2 && det (p[s[s[0]-1]], p[s[s[0]]], p[i]) <= 0)
            s[0]--;
        s[++s[0]] = i;
    }

    fout << fixed << setprecision (15);
    fout << s[0] << '\n';
    for (i = 1; i<=s[0]; i++)
        fout << p[s[i]].x << ' ' << p[s[i]].y << '\n';
    return 0;
}