Cod sursa(job #3030894)

Utilizator razvanalexrotaruRazvan Alexandru Rotaru razvanalexrotaru Data 17 martie 2023 22:47:26
Problema Infasuratoare convexa Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <bits/stdc++.h>
#include <fstream>
#define cin fin
#define cout fout
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct puncte
{
    double x,y;
};
puncte pct[120008];
bool compar(puncte a,puncte b)
{
    return a.y<b.y || a.y==b.y && a.x<b.x;
}
int calculare(double x1,double y1,double x2,double y2,double x3,double y3)
{
    double aux=x1*y2-x3*y2+x2*y3-y3*x1-x2*y1+y1*x3;
    if(aux>=0)
        return 1;
    return -1;
}
int cnt,sol[120008],n,i;
double pct1,pct2;
int main()
{
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>pct[i].x>>pct[i].y;
    }
    sort(pct+1,pct+n+1,compar);
    sol[0]=n;
    sol[++cnt]=1;
    for(i=2;i<=n;i++)
    {
        while(calculare(pct[sol[cnt-1]].x,pct[sol[cnt-1]].y,pct[sol[cnt]].x,pct[sol[cnt]].y,pct[i].x,pct[i].y)==1 && cnt>=1)
        {
            cnt--;
        }
        if(cnt!=0)
        sol[++cnt]=i;
        else
        cnt++;
    }
    for(i=n-1;i>=1;i--)
    {
        while(calculare(pct[sol[cnt-1]].x,pct[sol[cnt-1]].y,pct[sol[cnt]].x,pct[sol[cnt]].y,pct[i].x,pct[i].y)==1 && cnt>=1)
        {
            cnt--;
        }
        if(cnt!=0)
        sol[++cnt]=i;
        else
        cnt++;
    }
    cnt--;
    cout<<cnt<<'\n';
    for(i=cnt;i>=1;i--)
    {
        cout<<fixed<<setprecision(9)<<pct[sol[i]].x<<" "<<pct[sol[i]].y<<'\n';
    }
    return 0;
}