Cod sursa(job #2936686)

Utilizator Botnaru_VictorBotnaru Victor Botnaru_Victor Data 9 noiembrie 2022 11:19:11
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>
#define nmax 120003
#define float double
#define inf FLT_MAX
#define pi 3.14159
using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct pt{
    float x,y;
};

int st;
pt s[nmax];

float cross(const pt &a, const pt &b, const pt  &c)
{
    float cr=(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
    //g<<a.x<<','<<a.y<<' '<<b.x<<','<<b.y<<' '<<c.x<<','<<c.y<<' '<<cr<<'\n';
    return cr;
}

bool cmp(const pt &a, const pt &b)
{
    return cross(s[0],a,b)<0;
}

int n;
pt stk[nmax];
int k;

int main()
{
    f>>n;
    for(int i=0;i<n;i++)
    {
        f>>s[i].x>>s[i].y;
        if(s[i].x<s[st].x) st=i;
        else if(s[i].x==s[st].x&&s[i].y<s[st].y) st=i;
    }
    swap(s[0],s[st]);
    sort(s+1,s+n,cmp);
    stk[k++]=s[0];
    for(int i=1;i<n;i++)
    {
        auto e=s[i];
        //if(e.x==st.x&&e.y==st.y) continue;
        
        while(k>=2&&cross(stk[k-2],stk[k-1],e)>0) {k--;}
        stk[k++]=e;
        //g<<e.x<<','<<e.y<<','<<k<<'\n';
    }
    g<<k<<'\n';
    for(int i=k-1;i>=0;i--)
    {
        g<<fixed<<setprecision(6)<<stk[i].x<<' '<<stk[i].y<<'\n';
    }
    

    return 0;
}