Cod sursa(job #2869013)

Utilizator mihneazzzMacovei Daniel mihneazzz Data 11 martie 2022 12:06:56
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>
#define N 120005
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
    double x,y;
};
int n,top;
punct a[N],stv[N],O;
/**
ABxAC=[(xB-xA)i+(yB-yA)j]x[(xC-xA)i+(yC-yA)j]
(xB-xA)(yC-yA)k-(yB-yA)(xC-xA)k
*/
double produs_vectorial(punct A,punct B,punct C)
{
    return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
inline bool comp(punct a, punct b){

    return atan2(a.x - O.x, a.y - O.y) < atan2(b.x - O.x, b.y - O.y);

}
int main()
{
    int i,poz=1;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>a[i].x>>a[i].y,O.x+=a[i].x,O.y+=a[i].y;
    O.x/=n;O.y/=n;
    sort(a+1,a+n+1,comp);
    stv[1]=a[1];stv[2]=a[2];
    top=2;
    for(i=3;i<=n;i++)
    {
        while(top>=2 && produs_vectorial(stv[top-1],stv[top],a[i])>0) top--;
        stv[++top]=a[i];
    }
    fout<<top<<"\n";
    poz=1;
    for(i=1;i<=top;i++) stv[i+top]=stv[i];
    for(i=2;i<=top;i++)
        if(stv[i].y<stv[poz].y || stv[i].y==stv[poz].y && stv[i].x<stv[poz].x) poz=i;
    for(i=poz+top;i>=poz+1;i--)
        fout<<fixed<<setprecision(9)<<stv[i].x<<" "<<stv[i].y<<"\n";
    return 0;
}