Cod sursa(job #1667796)

Utilizator malina_floreaMalina Florea malina_florea Data 29 martie 2016 11:27:17
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.04 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 b.x*a.y < a.x*b.y || (a.x*b.y==b.x*a.y && ra>rb);
}

void citire();
void translatie();
void rez();
int prod(punct, punct, punct);

int n, nrs;
punct v[DMAX], start;
punct s[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+start.x, v[i].y+start.y);
//    
    fprintf(fout, "%d\n", nrs);
    for (i=0; i<nrs; i++)
        fprintf(fout, "%lf %lf\n", s[i].x+start.x, s[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, ok;
    
    s[nrs++]=v[n-1];
    s[nrs++]=v[0];
    
    for (i=1; i<n-1; i++)
    {
        ok=prod(s[nrs-2], s[nrs-1], v[i]);
        if (ok==0) //puncte coliniare
        {
            nrs--;
            s[nrs++]=v[i];
        }
        else
        {
            if (ok>0) //la stanga
                s[nrs++]=v[i];
            else //la dreapta
            {
                while (ok<=0 && nrs>1)
                {
                    nrs--;
                    ok=prod(s[nrs-2], s[nrs-1], v[i]);
                }
                s[nrs++]=v[i];
            }
        }
    }
}

int prod(punct v1, punct v2, punct v3)
{
    return (v2.x-v1.x)*(v3.y-v1.y)-(v3.x-v1.x)*(v2.y-v1.y);
}