Cod sursa(job #1185692)

Utilizator heracleRadu Muntean heracle Data 16 mai 2014 13:24:24
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <cstdio>
#include <cmath>
#include <algorithm>

FILE* in;
FILE* out;

int n;

const int Q=120001;

struct point{
    double x,y;
    double tan;
} v[Q];

bool cmp(point a, point b)
{
    return a.tan<b.tan;
}

point stv[Q];
int nr;

bool add( int x)
{
    long double t1,t2;
    t1=(stv[nr].x-stv[nr-1].x)*(v[x].y-stv[nr-1].y);

    t2=(v[x].x-stv[nr-1].x)* (stv[nr].y-stv[nr-1].y);

    if(t1>t2)
        return 1;
    return 0;

}

int main()
{
    in=fopen("infasuratoare.in","r");
    out=fopen("infasuratoare.out","w");

    fscanf(in,"%d",&n);

    for(int i=1; i<=n; i++)
    {
        fscanf(in,"%lf%lf",&v[i].x,&v[i].y);
        v[i].tan=atan2(v[i].x,v[i].y);
    }

    std::sort(v+1,v+n+1,cmp);

    for(int i=1; i<=n; i++)
    {
        if(add(i)==0)
        {
            stv[nr].tan=v[i].tan;
            stv[nr].x=v[i].x;
            stv[nr].y=v[i].y;
        }
        else
        {
            nr++;
            stv[nr].tan=v[i].tan;
            stv[nr].x=v[i].x;
            stv[nr].y=v[i].y;
        }
    }

    for(int i=1; i<=nr; i++)
    {
        fprintf(out,"%lf %lf\n",stv[i].x,stv[i].y);
    }

    return 0;
}