Cod sursa(job #1667716)

Utilizator malina_floreaMalina Florea malina_florea Data 29 martie 2016 10:16:27
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#define DMAX 120010
#define INF 1000000005
using namespace std;
FILE * fin = fopen("infasuratoare.in", "r");
FILE * fout = fopen("infasuratoare.out", "w");

struct punct{
    double x, y;
};

bool compare(punct a, punct b)
{
    int ra=sqrt(a.x*a.x+a.y*a.y), rb=sqrt(b.x*b.x+b.y*b.y);
    return a.x*b.y<b.x*a.y || (a.x*b.y==b.x*a.y && ra>rb);
}

void citire();
void translatie();
void rez();

int n, nrsol;
punct v[DMAX], start;
punct sol[DMAX];

int main()
{
    int i;
    
    citire();
    translatie();
    sort(v, v+n, compare);
    
    rez();
    
//    fprintf(fout, "%lf %lf\n\n", start.x, start.y);
//    
//    for (i=0; i<n; i++)
//        fprintf (fout, "%lf %lf\n", v[i].x, v[i].y);
//    
    fprintf(fout, "%d\n", nrsol);
    for (i=nrsol-1; i>=0; i--)
        fprintf(fout, "%lf %lf\n", sol[i].x+start.x, sol[i].y+start.y);
    
    fclose(fin);
    fclose(fout);
    return 0;
}

void citire()
{
    int i;
    start.x=start.y=INF;
    
    fscanf(fin, "%d", &n);
    for (i=0; i<n; i++)
    {
        fscanf(fin, "%lf %lf", &v[i].x, &v[i].y);
        if (v[i].y<start.y || (start.y == v[i].y && v[i].x<start.x))
            start=v[i];
    }
}

void translatie()
{
    int i;
    for (i=0 ;i<n; i++){
        v[i].x-=start.x;
        v[i].y-=start.y;
    }
}

void rez()
{
    int i, m, nr;
    punct v1, v2, v3;
   
    v1=v[0];
    v2=v[1];
    sol[nrsol++]=v1;
    
    for (i=2; i<n; i++)
    {
        v3=v[i];
        
        if (v1.x-v2.x==0) m=0;
        else m=-(v1.y-v2.y)/(v1.x-v2.x);
        
        nr=(v2.y-v3.y)-m*(v2.x-v3.x);
        
        if (nr>0)
        {
            sol[nrsol++]=v2;
            v1=v2;
            v2=v3;
        }
        else
        {
            v2=v3;
        }
    }
    
    sol[nrsol].x=sol[nrsol].y=0;
    nrsol++;
}