Cod sursa(job #2553727)

Utilizator darisavuSavu Daria darisavu Data 22 februarie 2020 11:25:25
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int st[120005];
struct punct
{
    double x,y;
} a[120005],d;
int n,i,mn,nr;
double aa,bb;
bool egal(double x,double y)
{
    if((x-y<0.000000000001&&x-y>=0)||(y-x<0.000000000001&&y-x>=0)) return 1;
    return 0;
}
double det( punct A, punct B, punct C)
{
    return (A.x - B.x) * (A.y - C.y) - (A.y - B.y) * (A.x - C.x);
}
double unghi(double x, double y)
{
    double p1;
    if(egal(aa+x,0)) p1=0;
    else p1=(bb-y)/(aa+x);
    return p1;
}
double compar(punct a,punct b)
{
    double p1,p2;
    if(egal(aa+a.x,0)) p1=(bb-a.y);
    else p1=(bb-a.y)/(aa+a.x);
    if(egal(aa+b.x,0)) p2=(bb-b.y);
    else p2=(bb-b.y)/(aa+b.x);

    if(p1==p2) return(bb-a.y<bb-b.y);
    if(p1>=0&&p2>=0)
    {
        return p1>p2;
    }
    else if(p1>=0&&p2<0) return 1;
    else if(p1<0&&p2>=0) return 0;
    else
    {
        return p1>p2;
    }
}
int main()
{
    f>>n;
    f>>a[1].x>>a[1].y;
    mn=1;
    for(i=2; i<=n; i++)
    {
        f>>a[i].x>>a[i].y;
        if(a[i].x<a[mn].x)
        {
            mn=i;
        }
        else if(egal(a[i].x,a[mn].x)&&a[i].y<a[mn].y) mn=i;
    }
    if(a[mn].x>0) aa=a[mn].x;
    else aa=-a[mn].x;
    bb=a[mn].y;
    d=a[mn];
    sort(a+1,a+n+1,compar);
    st[1]=1;
    st[2]=2;
    nr=2;
    for(i=3; i<=n; i++)
    {
        while(nr>=2&&det(a[st[nr]],a[st[nr-1]],a[i])>0) nr--;
        st[++nr]=i;
    }
    g<<nr+1<<'\n';
    g<<d.x<<" "<<d.y<<'\n';
    for(i=1; i<=nr; i++) g<<a[st[i]].x<<" "<<a[st[i]].y<<'\n';
    return 0;
}