Cod sursa(job #2520535)

Utilizator Groza_Iulia_DianaGroza Iulia Diana Groza_Iulia_Diana Data 9 ianuarie 2020 15:21:41
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <bits/stdc++.h>
#define p pair<double, double>
#define x first
#define y second

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

int n;
p a[150005], h[150005];

bool s(p a, p b, p c)
{
	return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x)<0;
}

int main()
{
    fin >> n;
    for(int i=0; i<n; i++)
        fin >> a[i].x >> a[i].y;
    sort(a, a+n);
    reverse_copy(a, a+n-1, a+n);
    int j=0;
    for(int i=0; i<2*n-1; h[j++]=a[i++])
        while(j>1 && s(h[j-2], h[j-1], a[i]))
            j--;
    fout << --j << "\n";
    for(int i=0; i<j; i++)
        fout << fixed << setprecision(9) << h[i].x << " " << h[i].y << "\n";
    return 0;
}