Cod sursa(job #3299454)

Utilizator hhhhhhhAndrei Boaca hhhhhhh Data 6 iunie 2025 16:22:00
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,nr;
struct punct
{
    long double x,y;
}v[120012],primul,act;
long double aria(punct a,punct b,punct c)
{
    a.x-=c.x;
    a.y-=c.y;
    b.x-=c.x;
    b.y-=c.y;
    return (a.x*b.y-a.y*b.x)/2.0;
}
bool crt(punct a,punct b)
{
    if(aria(primul,a,b)!=0)
		return aria(primul,a,b)>0;
	return a.y<b.y;
}
stack<punct> s,rez;
int main()
{
    fin>>n;
    fin>>v[1].x>>v[1].y;
    primul=v[1];
    for(int i=2; i<=n; i++)
    {
        fin>>v[i].x>>v[i].y;
        if(v[i].y<primul.y)
            primul=v[i];
        else if(v[i].y==primul.y)
            primul.x=min(primul.x,v[i].x);
    }
    sort(v+1,v+n+1,crt);
    s.push(primul);
    for(int i=1; i<=n; i++)
    {
        if(!(primul.x==v[i].x && primul.y==v[i].y) && s.size()==1)
            s.push(v[i]);
        else if(!(primul.x==v[i].x && primul.y==v[i].y))
        {
            while(1 && s.size()>=2)
            {
                act=s.top();
                s.pop();
                if(!s.empty() && aria(s.top(),act,v[i])>=0)
                {
                    s.push(act);
                    break;
                }
            }
            s.push(v[i]);
        }
    }
    memset(v,0,sizeof(v));
    while(!s.empty())
    {
        rez.push(s.top());
        s.pop();
        nr++;
    }
    fout<<nr<<'\n';
    while(!rez.empty())
    {
        fout<<fixed<<setprecision(6)<<rez.top().x<<' '<<rez.top().y<<'\n';
        rez.pop();
    }
    return 0;
}