Cod sursa(job #2547240)

Utilizator aser.cobaschiCobaschi Aser aser.cobaschi Data 15 februarie 2020 10:23:59
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>
#define punct pair<double,double>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int N = 120010;
double x,y;
int n,m;
punct p[N];
bool crit(punct,punct);
double det(punct,punct,punct);
int main()
{   f>>n;
    for(int i=0;i<=n;i++)
    {
        f>>x>>y;
        p[i]=make_pair(x,y);
        if(p[i]<p[0]) swap(p[i],p[0]);
    }
    sort(p+1,p+n,crit);
    m=1;
    for(int i=2;i<n;i++)
    {
        while(det(p[m-1],p[m],p[i])<0)
            m--;
        p[++m]=p[i];
    }
    g<<m+1<<'\n';
    for(int i=0;i<=m;i++)
        g<<fixed<<setprecision(10)<<p[i].first<<' '<<p[i].second<<'\n';
    return 0;
}
double det(punct A,punct B,punct C)
{
    double a1,b1;tie(a1,b1)=A;
    double a2,b2;tie(a2,b2)=B;
    double a3,b3;tie(a3,b3)=C;
    return a1*b2+a2*b3+a3*b1-(a1*b3+a3*b2+a2*b1);
}
bool crit(punct A,punct B)
{
    return det(p[0],A,B)>=0;
}