Cod sursa(job #2110751)

Utilizator vancea.catalincatalin vancea.catalin Data 21 ianuarie 2018 12:34:17
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include<algorithm>
#include<iostream>
#include<fstream>
#include<iomanip>
#include<vector>
#define INF 1100000000
#define DN 120100
using namespace std;
fstream fin("infasuratoare.in",ios::in),fout("infasuratoare.out",ios::out);
double x=INF,y=INF,a,b;
int n,lr=0;
class point
{
public:
    double x,y;
} p[DN],r[DN];
double det(point p,point a,point b)
{
    return (p.x*a.y+a.x*b.y+p.y*b.x-p.y*a.x-a.y*b.x-b.y*p.x);
}
bool cmp(point a,point b)
{
    return det(p[0],a,b)>=0;
}
int main()
{
    int i,ind;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>a>>b;
        if(x>a  || (x==a && y>b))
        {
            x=a;y=b;ind=i;
        }
        p[i]={a,b};
    }
    
    p[0]=p[ind];p[ind]=p[n];
    sort(p+1,p+n,cmp);
    r[1]=p[0];lr=1;
    
    for(i=1;i<n;i++)
    {
        while(lr>1 && det(r[lr-1],r[lr],p[i])<0) lr--;
        r[++lr]=p[i];
    }
    fout<<lr<<"\n";
    for(i=1;i<=lr;i++) fout<<fixed<<setprecision(12)<<r[i].x<<" "<<r[i].y<<"\n";
}