Cod sursa(job #2211422)

Utilizator dobrandreiAndrei Dobra dobrandrei Data 10 iunie 2018 12:02:01
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
FILE *in,*out;

int n;
bool used[120002];
int st[120002];

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

bool how (name a, name b)
{
    if(a.x!=b.x)
        return a.x<b.x;
    return a.y<b.y;
}


void read(){
    fscanf(in,"%d",&n);
    for(int i=1;i<=n;i++)
        fscanf(in,"%lf %lf",&v[i].x,&v[i].y);
    sort(v+1,v+n+1,how);
}

double determinant (name a, name b, name c){
    return ((a.x*b.y+b.x*c.y+c.x*a.y)-(b.y*c.x+c.y*a.x+a.y*b.x));
}

int main(){
    in=fopen("infasuratoare.in","r");
    out=fopen("infasuratoare.out","w");

    read();

    int vf=2,poz=3,ok=1;
    st[1]=1,st[2]=2;
    used[2]=1;

    while(!used[1]){
        while(used[poz]){
            if(poz==n)
                ok=-1;
            poz+=ok;
        }
        while(vf>=2 && determinant(v[st[vf-1]],v[st[vf]],v[poz])<0){
            used[st[vf]]=0;
            vf--;
        }
        vf++;
        st[vf]=poz;
        used[poz]=1;
    }

    fprintf(out,"%d\n",vf-1);
    for(int i=2;i<=vf;i++)
        fprintf(out,"%6f %6f\n",v[st[i]].x,v[st[i]].y);
    return 0;
}