Cod sursa(job #3245373)

Utilizator Dumiboidumitrache rares Dumiboi Data 28 septembrie 2024 18:21:53
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.26 kb
#include <fstream>
#include <algorithm>
#include <stack>
#include <iomanip>
using namespace std;
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
struct punct{
    double x,y;
}v[12001],p1[12001],p2[12001],drum[12001];
stack<punct> s;
bool cmp(punct a,punct b)
{
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;

}
int arie(punct a,punct b,punct c)
{
    double area=a.x*b.y+b.x*c.y+c.x*a.y-b.y*c.x-c.y*a.x-a.y*b.x;
    if(area>0)
        return 1;
    else
        return -1;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>v[i].x>>v[i].y;
    sort(v+1,v+1+n,cmp);
   /// for(int i=1;i<=n;i++)
        ///cout<<v[i].x<<" "<<v[i].y<<"\n";
    punct prim=v[1],ult=v[n];
    int cnt1=0,cnt2=0;
    for(int i=2;i<=n-1;i++)
    {
        ///selectam punctele, sub dr -> p1 peste dr -> p2
        if(arie(prim,ult,v[i])==-1)
            cnt1++,p1[cnt1]=v[i];
        else
            cnt2++,p2[cnt2]=v[i];
    }
    ///stiva pt alea de sub
   /* for(int i=1;i<=cnt1;i++)
        cout<<p1[i].x<<" "<<p1[i].y<<"\n";
    cout<<"\n";
    for(int i=1;i<=cnt2;i++)
        cout<<p2[i].x<<" "<<p2[i].y<<"\n"*/
    punct punct1,punct2,punct3;
    punct1=prim;
    punct2=p1[1];
    s.push(punct2);
    for(int i=2;i<=cnt1;i++)
    {
        punct3=p1[i];
        while(s.size()>=2 and arie(punct1,punct2,punct3)==-1)
            s.pop();
        s.push(punct3);
        punct1=punct2;
        punct2=punct3;
    }
    int cntd=0,c=s.size(),c1=c;
    while(!s.empty())
    {
        cntd++;
        drum[c]=s.top();
        c--;
        s.pop();
    }
    cntd++;
    drum[cntd]=ult;
    c1++;
    punct1=ult;
    punct2=p2[cnt2];
    s.push(punct2);
    for(int i=cnt2-1;i>=1;i--)
    {
        punct3=p2[i];
        while(s.size()>=2 and arie(punct1,punct2,punct3)==-1)
            s.pop();
        s.push(punct3);
        punct1=punct2;
        punct2=punct3;
    }
    c=s.size();
    while(!s.empty())
    {
        cntd++;
        drum[c1+c]=s.top();
        c--;
        s.pop();
    }
    cntd++;
    drum[cntd]=prim;
    cout<<cntd<<"\n";
    for(int i=1;i<=cntd;i++)
        cout<<fixed<<setprecision(6)<<drum[i].x<<" "<<drum[i].y<<"\n";
    return 0;
}