Cod sursa(job #2558150)

Utilizator dimi999Dimitriu Andrei dimi999 Data 26 februarie 2020 12:43:49
Problema Infasuratoare convexa Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
using namespace std;

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


int n, ok, s[120005];
bool viz[120005];

struct Point
{
    double x, y;
}v[120005];

inline bool cmp(const Point &a, const Point &b)
{
    if(a.y == b.y)
        return a.y < b.y;
    return a.x < b.x;
}

double rez(Point A, Point B, Point C)
{
    return (B.x - A.x)*(C.y - A.y) - (B.y - A.y)*(C.x - A.x);
}

int top;

void rezolva()
{
    s[1] = 1;
    s[2] = 2;
    top = 2;
    viz[2] = true;
    int i = 3;

    int pas = 1;

    while(!viz[1])
    {
        while(viz[i])
        {
            if(i == n)
                pas = -1;
            i += pas;
        }
        while(rez(v[s[top - 1]],v[s[top]],v[i]) < 0 && top >= 2)
            viz[s[top]] = 0, top--;
        s[++top] = i;
        viz[i] =1;
    }
    top --;
}


int main()
{
    fin >> n;

    for(int i = 1; i <= n; i++)
        fin >> v[i].x >> v[i].y;

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

    rezolva();

    fout << top << '\n';

    for(int i = 2; i <= top + 1; i++)
        fout << fixed << setprecision(8) << v[s[i]].x << " " << fixed << setprecision(8) << v[s[i]].y <<'\n';


    return 0;
}