Cod sursa(job #2548014)

Utilizator tavi255Varzaru Octavian Stefan tavi255 Data 16 februarie 2020 00:30:59
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
//#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int Max=120005;
int n;
struct pct
{
    double x,y;
}p[Max],s[Max];
double cross(pct q,pct r,pct t)
{
    return (r.y-q.y)*(t.x-q.x)-(t.y-q.y)*(r.x-q.x);
}
bool sortare(pct a,pct b)
{
    return (cross(p[1],a,b)<0);
}
int main()
{
    in>>n;
    for(int i=1;i<=n;i++)
        in>>p[i].x>>p[i].y;
    int poz=1;
    for(int i=2;i<=n;i++)
        if(p[i].x<p[poz].x || (p[i].x==p[poz].x && p[i].y<p[poz].y))
        poz=i;
    swap(p[1],p[poz]);
    sort(p+1,p+n+1,sortare);
    int nr=0;
    s[++nr]=p[1];
    s[++nr]=p[2];
    for(int i=3;i<=n;i++)
    {
        while(nr>=2 && cross(s[nr-1],s[nr],p[i])>0)
            nr--;
        s[++nr]=p[i];
    }
    out<<nr<<"\n";
    out<<fixed;
    for(int i=1;i<=nr;i++)
        out<<setprecision(6)<<s[i].x<<" "<<s[i].y<<"\n";
    return 0;
}