Cod sursa(job #943656)

Utilizator myshuSpatariu Mihai-Constantin myshu Data 26 aprilie 2013 07:10:03
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
FILE *f=fopen("infasuratoare.in","r");
FILE *g=fopen("infasuratoare.out","w");
int n,vf,xuri[12000];
typedef struct {int x,y;}NOD;
NOD st[12000],p[12000];
void citire()
{
    fscanf (f,"%d", &n);
    for (int i = 1; i <= n; ++i)
		fscanf(f,"%d",&xuri[i]);
	int ygrec;
	for (int i=1;i<=n;++i){
		fscanf(f,"%d",&ygrec);
		p[i].x=xuri[i];
		p[i].y=ygrec;
	}
}
bool cmp (NOD a, NOD b)
{
    return ((a.y < b.y) || (a.y == b.y && a.x < b.x));
}
float det(NOD a, NOD b, NOD c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
void convex_hull()
{
    sort(p+1,p+n+1,cmp);
    st[1]=p[1];
    st[2]=p[2];
    vf=2;
    int i;
    for (i=3;i<=n;i++)
    {   while (det(st[vf-1],st[vf],p[i])>0)
            vf--;
        st[++vf]=p[i];
    }
    for (i=n-1;i>=1;i--)
    {
        while (det(st[vf-1],st[vf],p[i])>0)
            vf--;
        st[++vf]=p[i];
    }
}
double aria;
void afis()
{
	
    for (int i = vf; i >= 2; --i)
        fprintf (g,"%.12lf %.12lf\n", st[i].x, st[i].y);
	
	//for (int i=2;i<vf;i++)
	//	aria=aria+(st[i].x*st[i+1].y-st[i+1].x*st[i].y)/2.00;
	
}
int main()
{
    citire();
    convex_hull();
	afis();
    fprintf(g,"%.2lf",aria*-1);
    return 0;
}