Cod sursa(job #2287888)

Utilizator ciutanpCiuta Andrei Calin ciutanp Data 22 noiembrie 2018 17:11:22
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include<bits/stdc++.h>
using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct Puncte{
double x,y;}v[120002],s[120002];

int l,n;

bool cmp(Puncte A,Puncte B)
{
    if(A.x==B.x)
        return A.y<B.y;
    return A.x<B.x;
}

double cros(Puncte A,Puncte B,Puncte C)
{
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

void MRGA()
{
    for(int i=1;i<=n;++i)
    {
        while(l>1 && cros(s[l-1],s[l],v[i])<=0)
            l--;
        s[++l]=v[i];
    }
    int mic=l;
    for(int i=n;i>=1;--i)
    {
        while(l>mic && cros(s[l-1],s[l],v[i])<=0)
            l--;
        s[++l]=v[i];
    }
    l--;
}

int main()
{
    f>>n;
    for(int i=1;i<=n;++i)
        f>>v[i].x>>v[i].y;
    sort(v+1,v+n+1,cmp);
    MRGA();
    g<<l<<'\n';
    for(int i=1;i<=l;++i)
        g<<s[i].x<<' '<<s[i].y<<'\n';
}