Cod sursa(job #2768432)

Utilizator xXoctavianXxStanescu Matei Octavian xXoctavianXx Data 10 august 2021 18:26:20
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.92 kb
#include <bits/stdc++.h>

using namespace std;

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

struct punct
{
    double x,y;
};

punct v[120005];
punct pt= {1e9+7,1e9+7};
int n,nr;
punct rasp[120005];

bool comp(punct a, punct b)
{
    ///(a.y-pt.y)/(a.x-pt.x)<(b.y-pt.y)/(b.x-pt.x)
    ///(a.y-pt.y)*(b.x-pt.x)<(b.y-pt.y)*(a.x-pt.x)
    if(a.x==pt.x && a.y==pt.y) return 1;
    if(b.x==pt.x && b.y==pt.y) return 0;
    return ( (a.y-pt.y)*(b.x-pt.x)-(b.y-pt.y)*(a.x-pt.x)<0 );
}

bool in_exterior(punct a, punct b, punct p)
{
    if(a.x<b.x)
    {
        double gr=(b.y-a.y)/(b.x-a.x);
        double h=b.y-gr*b.x;
        if(gr*p.x+h>=p.y) return 1;
        return 0;
    }
    else if(a.x>b.x)
    {
        double gr=(b.y-a.y)/(b.x-a.x);
        double h=b.y-gr*b.x;
        if(gr*p.x+h<=p.y) return 1;
        return 0;
    }
    else
    {
        if(a.y<b.y)
        {
            if(p.x>=a.x) return 1;
            return 0;
        }
        else if(a.y>b.y)
        {
            if(p.x<=a.x) return 1;
            return 0;
        }
    }
}

int main()
{
    fin>>n;
    for(int i=0; i<n; i++)
    {
        fin>>v[i].x>>v[i].y;
        if(pt.x>v[i].x) pt=v[i];
        else if(pt.x==v[i].x && pt.y>v[i].y) pt=v[i];
    }
    sort(v,v+n,comp);

    for(int i=0; i<n; i++)
    {
        //cout<<v[i].x<<" "<<v[i].y<<"\n";
    }
    rasp[nr++]=v[0];
    rasp[nr++]=v[1];
    for(int i=2; i<n; i++)
    {
        punct a=rasp[nr-2];
        punct b=rasp[nr-1];
        while(nr>1 && in_exterior(a,b,v[i]))
        {
            //cout<<a.x<<" "<<a.y<<": "<<b.x<<" "<<b.y<<": "<<v[i].x<<" "<<v[i].y<<"\n";
            nr--;
            a=rasp[nr-2];
            b=rasp[nr-1];
        }
        rasp[nr++]=v[i];
    }
    fout<<nr<<"\n";
    for(int i=0; i<nr; i++) fout<<fixed<<setprecision(6)<<rasp[i].x<<" "<<rasp[i].y<<"\n";
    return 0;
}