Cod sursa(job #3168852)

Utilizator proflaurianPanaete Adrian proflaurian Data 13 noiembrie 2023 15:54:38
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int N = 120010;
typedef pair<double,double> punct;
punct P[N],S[N];
double det(punct A,punct B,punct C)
{
    double ret = A.X*B.Y+B.X*C.Y+C.X*A.Y-(A.Y*B.X+B.Y*C.X+C.Y*A.X);
    return ret;
}
bool crit(punct A,punct B)
{
    return det(P[0],A,B)>=0;
}
int n,t;
int main()
{
    f>>n;
    int iMin=0;
    for(int i=0;i<n;i++)
    {
        double x,y;
        f>>x>>y;
        P[i]=make_pair(x,y);
        if(P[i]<P[iMin]) /// memorez pozitia unde perechea e cea mai mica
            iMin=i;
    }
    swap(P[0],P[iMin]);
    sort(P+1,P+n,crit);
    S[++t]=P[0];S[++t]=P[1];
    for(int i=2;i<n;i++)
    {
        while(det(S[t-1],S[t],P[i])<0)
            t--;
        S[++t]=P[i];
    }
    g<<t<<'\n';
    for(int i=1;i<=t;i++)
        g<<fixed<<setprecision(10)<<S[i].X<<' '<<S[i].Y<<'\n';
    return 0;
}