Cod sursa(job #2260014)

Utilizator unknownpersonBidasca Carina Georgiana unknownperson Data 14 octombrie 2018 11:28:50
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<double,double> punct;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,i,top;

punct v[120001];
double det(punct A,punct B,punct C)
{
    return A.X*B.Y+B.X*C.Y+C.X*A.Y-(A.Y*B.X+B.Y*C.X+C.Y*A.X);
}
bool cmp(punct A,punct B)
{
    return det(v[0],A,B)>0;
}
int main()
{
    f>>n;
    for(i=0; i<n; i++)
    {
        double x,y;
        f>>x>>y;
        v[i]=make_pair(x,y);
        if(v[i]<=v[0])
            swap(v[i],v[0]);
    }
    sort(v+1,v+n,cmp);
    top=1;
    for(i=2;i<n;i++)
    {
        while(det(v[top-1],v[top],v[i])<=0)
            top--;
        v[++top]=v[i];
    }
    g<<top+1<<'\n';
    for(i=0;i<=top;i++)
        g<<fixed<<setprecision(8)<<v[i].X<<' '<<v[i].Y<<'\n';
    return 0;
}