Cod sursa(job #2922784)

Utilizator puica2018Puica Andrei puica2018 Data 10 septembrie 2022 08:41:45
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct Point
{
    double x;
    double y;
};

int n;
Point a[120005];
bool viz[120005];

bool cmp(Point A,Point B)
{
    if(A.y==B.y)
        return A.x<B.x;
    return A.y<B.y;
}

long long f(Point A,Point B,Point C)
{
    int a,b,c;
    a=B.y-A.y;
    b=A.x-B.x;
    c=1LL*A.y*(B.x-A.x)-1LL*A.x*(B.y-A.y);
    return 1LL*a*C.x+1LL*b*C.y+c;
}

int s[120005],k;

int main()
{
    fin>>n;
    for(int i=1; i<=n; i++)
        fin>>a[i].x>>a[i].y;
    /// cout<<f({1,0},{0,1},{0,0});
    sort(a+1,a+n+1,cmp);
    s[++k]=1;
    s[++k]=2;
    viz[2]=1;
    for(int i=3; i<=n; i++)
    {
        while(k>=2 && f(a[s[k-1]],a[s[k]],a[i])>=0)
        {
            viz[s[k]]=0;
            k--;
        }
        viz[i]=1;
        s[++k]=i;
    }
    for(int i=n; i>=1; i--)
    {
        if(viz[i]==0)
        {
            while(k>=2 && f(a[s[k-1]],a[s[k]],a[i])>=0)
                k--;
            s[++k]=i;
        }
    }
    fout<<k-1<<"\n";
    for(int i=1; i<k; i++)
        fout<<setprecision(12)<<fixed<<a[s[i]].x<<" "<<a[s[i]].y<<"\n";
    return 0;
}