Cod sursa(job #2535218)

Utilizator PaterucAPetruc Andrei Stefan PaterucA Data 31 ianuarie 2020 17:29:25
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>
#define ld long double
#define X first
#define Y second
#define punct pair<ld,ld>

using namespace std;

ifstream inf("infasuratoare.in");
ofstream outf("infasuratoare.out");
const int N = 120010;
int n,top;
pair<ld,ld> p[N];
ld det(punct a,punct b,punct c)
{
    return a.X*b.Y+b.X*c.Y+c.X*a.Y-(a.X*c.Y+c.X*b.Y+b.X*a.Y);
}
bool crit(pair<ld,ld> a, pair<ld,ld> b)
{
    ld aux=det(p[0],a,b);
    if(aux>0.0)return true;
    return false;
}

int main()
{
    inf>>n;
    for(int i=0; i<n; i++)
    {
        ld x, y;
        inf>>x>>y;
        p[i]=make_pair(x,y);
        if(p[i]<p[0])
            swap(p[0], p[i]);
    }

    sort(p+1, p+n, crit);
    top=1;
    for(int i=2;i<n;i++)
    {
        while(det(p[top-1],p[top],p[i])<0.0)
            top--;
        p[++top]=p[i];
    }
    outf<<top+1<<'\n';
    for(int i=0;i<=top;i++)
        outf<<fixed<<setprecision(12)<<p[i].X<<' '<<p[i].Y<<'\n';
    return 0;
}