Cod sursa(job #2294330)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 2 decembrie 2018 11:35:27
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <cstdio>
#include <algorithm>
#define DIM 120001

using namespace std;
struct punct{
    double x,y;
};
punct v[DIM],s[DIM];
double arie (punct a,punct b,punct c){
    return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
}
int cmp (punct a,punct b){
    punct c;
    c.x=0;
    c.y=0;
    if (arie (c,a,b)!=0)
        return arie (c,a,b)>0;
    return a.x*a.x+a.y*a.y > b.x*b.x+b.y*b.y;
}
int main()
{
    FILE *fin=fopen ("infasuratoare.in","r");
    FILE *fout=fopen ("infasuratoare.out","w");
    int n,i,j,mini,elem;
    fscanf (fin,"%d",&n);
    mini=0;
    v[0].x=1.0*1000000000;
    v[0].y=1.0*1000000000;
    for (i=1;i<=n;i++){
        fscanf (fin,"%lf%lf",&v[i].x,&v[i].y);
        if (v[i].y<v[mini].y || (v[i].y==v[mini].y && v[i].x<v[mini].x))
            mini=i;
    }
    v[0]=v[mini];
    v[mini]=v[1];
    v[1]=v[0];
    for (i=1;i<=n;i++){
        v[i].x-=v[0].x;
        v[i].y-=v[0].y;
    }
    sort (v+2,v+n+1,cmp);
    for (j=3;j<=n;j++){
        if (arie (v[j],v[1],v[2]))
            break;
    }
    i=2;
    j--;
    while (i<j){
        swap(v[i],v[j]);
        i++;
        j--;
    }
    s[1]=v[1];
    s[2]=v[2];
    elem=2;
    for (j=3;j<=n;j++){
        while (elem>=2 && arie (s[elem-1],s[elem],v[j])<0) // nu il pot adauga aici pe v[j]
            elem--;
        s[++elem]=v[j];
    }
    fprintf (fout,"%d\n",elem);
    for (i=1;i<=elem;i++)
        fprintf (fout,"%lf %lf\n",s[i].x+v[0].x,s[i].y+v[0].y);
    return 0;
}