Cod sursa(job #1327967)

Utilizator stiharus96Dovan Andrei Dorinel stiharus96 Data 27 ianuarie 2015 18:08:57
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include<algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,a[120010],viz[120010],q;
struct punct
{
    float x,y;
}v[1200000];
bool cmp(punct a,punct b)
{
    if(a.x==b.x)
        return a.y<b.y;
    else
        return a.x<b.x;
}

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);
    a[1]=1;
    a[2]=2;viz[2]=1;q=2;
    for(int i=3;i<=n;i++)
    {
        if((v[a[q]].x-v[a[q-1]].x)*(v[i].y-v[a[q-1]].y)-(v[a[q]].y-v[a[q-1]].y)*(v[i].x-v[a[q-1]].x)<0)
            {a[++q]=i;
            viz[i]=1;

            }
        else
        {
            while((v[a[q]].x-v[a[q-1]].x)*(v[i].y-v[a[q-1]].y)-(v[a[q]].y-v[a[q-1]].y)*(v[i].x-v[a[q-1]].x)>=0)
                viz[q--]=0;
                a[++q]=i;
        }

    }

    for(int i=n;i>=1;i--)
        if((v[a[q]].x-v[a[q-1]].x)*(v[i].y-v[a[q-1]].y)-(v[a[q]].y-v[a[q-1]].y)*(v[i].x-v[a[q-1]].x)<0)
            {a[++q]=i;
            viz[i]=1;

            }
        else
        {
            while((v[a[q]].x-v[a[q-1]].x)*(v[i].y-v[a[q-1]].y)-(v[a[q]].y-v[a[q-1]].y)*(v[i].x-v[a[q-1]].x)>=0)
                viz[q--]=0;
                a[++q]=i;
        }
    g<<q-1<<'\n';
    g<<setprecision(6)<< fixed;
    for(int i=q-1;i>=1;i--)
        g<<v[a[i]].x<<" "<<v[a[i]].y<<'\n';
    return 0;
}