Cod sursa(job #2363991)

Utilizator dacianouaPapadia Mortala dacianoua Data 3 martie 2019 19:45:08
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define nmax 120000
#define pdd pair<double,double>
#define x first
#define y second
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,mn;
pdd v[nmax+5],s[nmax+5];
double det(pdd A,pdd B, pdd C)
{
    return A.x*B.y + B.x*C.y + C.x*A.y-C.y*A.x-B.y*C.x-A.y*B.x;
}
bool comp(pdd A, pdd B)
{
    return det(A,B,v[1])>=0;
}
int main()
{
    fin>>n;
    v[0] = {1e9+1,0};
    for(int i=1;i<=n;i++)
    {
        fin>>v[i].x>>v[i].y;
        if(v[i].x<v[mn].x || v[i].x==v[mn].x && v[i].y<v[mn].y)
            mn=i;
    }
    swap(v[mn],v[1]);
    sort(v+2,v+1+n,comp);
    int last=2;
    s[1]=v[1],s[2]=v[2];
    for(int i=3;i<=n;i++)
    {
        while(last>=2 && det(s[last-1],s[last],v[i])<0)last--;
        s[++last]=v[i];
    }
    fout<<last<<"\n";
    fout<<fixed<<setprecision(12);
    for(int i=1;i<=last;i++)
        fout<<s[i].x<<" "<<s[i].y<<"\n";
    return 0;
}