Cod sursa(job #3245405)

Utilizator Dumiboidumitrache rares Dumiboi Data 28 septembrie 2024 20:20:52
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.72 kb
#include <fstream>
#include <algorithm>
#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],st[12001];
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"*/
    int k;
    k=1;
    st[k]=prim;
    for(int i=1;i<=cnt1;i++)
    {
        while(k>1 and arie(st[k-1],st[k],p1[i])<0)
            k--;
        k++;
        st[k]=p1[i];
    }
    k++;
    int k2=k;
    st[k]=ult;
    for(int i=cnt2;i>=1;i--)
    {
        while(k>k2 and arie(st[k-1],st[k],p2[i])<0)
            k--;
        k++;
        st[k]=p2[i];
    }
    cout<<k<<"\n";
    for(int i=2;i<=k;i++)
        cout<<fixed<<setprecision(6)<<st[i].x<<" "<<st[i].y<<"\n";
    cout<<fixed<<setprecision(6)<<st[1].x<<" "<<st[1].y<<"\n";
    return 0;
}