Cod sursa(job #656040)

Utilizator Marius_mFMI-M2 Marius Melemciuc Marius_m Data 3 ianuarie 2012 20:44:12
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <stdio.h>
#include <algorithm>
#define Nmax 120001
#define inf 1000000002

using namespace std;

FILE *c,*d;

struct punct
{
    float x, y, p;
} a[Nmax], s[Nmax], x;

int h, n = 2, poz;

bool cmp(punct a, punct b)
{
    if (a.p>b.p)
        return false;
    return true;
}

void citire()
{
	int i;
    x.x = x.y = inf;
    fscanf (c,"%d ", &h);
    for (i=0;i<h;++i)
    {
        fscanf (c,"%f %f ", &a[i].x, &a[i].y);
        if (a[i].x < x.x || a[i].x == x.x && a[i].y < x.y)
        {
            x.x = a[i].x;
            x.y = a[i].y;
            poz = i;
        }
    }
    a[poz]=a[h-1];
    --h;
}

void afisare()
{
	int i;
    fprintf (d,"%d\n", n);
    for (i=0;i<n;++i)
        fprintf (d,"%f %f\n", s[i].x, s[i].y);
}

void panta()
{
	int i;
    for (i=0;i<h;++i)
        if (a[i].x==x.x)
            a[i].p=inf;
        else
            a[i].p=(a[i].y-x.y)/(a[i].x-x.x);
}

bool determinant(punct a,punct b,punct c)
{
    double det=a.x*b.y+a.y*c.x+b.x*c.y-a.y*b.x-b.y*c.x-c.y*a.x;
    if (det>=0)
        return 1;
    return 0;
}

void infasuratoare()
{
    s[0]=x;
    s[1]=a[0];
    for(i=1;i<h;++i)
        if (determinant(s[n-2],s[n-1],a[i]))
            s[n++]=a[i];
        else
        {
            while(determinant(s[n-2],s[n-1],a[i])==0)
                s[--n]=a[i];
            ++n;
        }
}

int main()
{
    c=fopen("infasuratoare.in","r");
	d=fopen("infasuratoare.out","w");
    citire();
    panta();
    sort(a,a+h,cmp);
    infasuratoare();
    afisare();
	fclose(c);
	fclose(d);
    return 0;
}