Cod sursa(job #2551915)

Utilizator ana_valeriaAna Valeria Duguleanu ana_valeria Data 20 februarie 2020 12:49:46
Problema Infasuratoare convexa Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.87 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
struct ura
{
    long double x,y;
};
ura coord[120010],st1[120010],st2[120010];
bool cmp(ura a,ura b)
{
    if (a.y>b.y)
        return true;
    else
        if (a.y<b.y)
            return false;
        else
            if (a.x>b.x)
                return true;
            else
                return false;
}
int pozitie(ura p3,ura p1,ura p2)
{
    long double a,b,c,s;
    a=p1.x*p2.y+p2.x*p3.y+p3.x*p1.y;
    b=p3.x*p2.y+p1.x*p3.y+p2.x*p1.y;
    c=a-b;
    s=1.0*1/2*c;
    if (s<0)///punctul e la dreapta
        return 1;
    else
        if (s>0)///punctul e la stanga
            return -1;
    return 0;
}
int main()
{
    int n,i,k1,k2;
    cin>>n;
    for (i=1; i<=n; i++)
        cin>>coord[i].x>>coord[i].y;
    sort (coord+1,coord+n+1,cmp);
    k1=0;
    st1[0]=coord[1];
    for (i=2; i<n; i++)
        if (pozitie(coord[i],coord[1],coord[n])==1)
        {
            while (pozitie(coord[i],st1[k1],st1[k1-1])==-1 && k1!=0)
                k1--;
            k1++;
            st1[k1]=coord[i];
        }
    k2=0;
    st2[0]=coord[n];
    for (i=n-1; i>=2; i--)
        if (pozitie(coord[i],coord[1],coord[n])==-1)
        {
            while (pozitie(coord[i],st2[k2],st2[k2-1])==-1 && k2!=0)
                k2--;
            k2++;
            st2[k2]=coord[i];
        }
    cout<<2+k1+k2<<"\n";
    cout<<fixed<<setprecision(12)<<coord[n].x<<" "<<fixed<<setprecision(12)<<coord[n].y<<"\n";
    for (i=1; i<=k2; i++)
        cout<<fixed<<setprecision(12)<<st2[i].x<<" "<<fixed<<setprecision(12)<<st2[i].y<<"\n";
    cout<<fixed<<setprecision(12)<<coord[1].x<<" "<<fixed<<setprecision(12)<<coord[1].y<<"\n";
    for (i=1; i<=k1; i++)
        cout<<fixed<<setprecision(12)<<st1[i].x<<" "<<fixed<<setprecision(12)<<st1[i].y<<"\n";
    return 0;
}