Cod sursa(job #2310714)

Utilizator bodea.georgianaBodea Georgiana bodea.georgiana Data 1 ianuarie 2019 21:40:39
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <stdio.h>
#define NMAX 120002
#include <bitset>
#include <algorithm>

using namespace std;
FILE *f,*g;

struct bla
{
    double x,y;
}v[NMAX];
int s[NMAX];
bitset <NMAX> viz;

bool how(bla A, bla B)
{
    if(A.x==B.x)
        return A.y<B.y;
    return A.x<B.x;
}
double determinant(bla A, bla B, bla C)
{
    double a=A.x,b=A.y,c=B.x,d=B.y,e=C.x,f=C.y;
    double delta=a*d+c*f+e*b-d*e-a*f-c*b;
    return delta;
}
void make(int n, int &top)
{
    int ok=1,i;
    s[1]=1;
    s[2]=2,viz[2]=1;
    top=2;
    i=3;
    while(!viz[1])
    {
        while(viz[i])
        {
            if(i==n) ok=-1;
            i+=ok;
        }
        while(determinant(v[s[top-1]],v[s[top]],v[i])<0 && top>=2)
            viz[s[top]]=0,--top;
///delta=0, punctele sunt coliniare
///delta<0, punctele constituie o orientare in sensul invers acelor de ceasornic
            ///sens trigonometric
///delta>0, punctele constituie o orientare in sensul acelor de ceasornic
        s[++top]=i;
        viz[i]=1;
    }
    --top;
}
int main()
{
    int top;
    f=fopen("infasuratoare.in","r");
    g=fopen("infasuratoare.out","w");
    int n;
    fscanf(f,"%d",&n);
    for(int i=1;i<=n;++i)
        fscanf(f,"%lf %lf",&v[i].x, &v[i].y);
    sort(v+1,v+n+1,how);
    make(n,top);
    fprintf(f,"%d\n",top);
    for(int i=2;i<=top+1;++i)
        fprintf(g,"%lf %lf\n",v[s[i]].x,v[s[i]].y);
    fclose(f);
    fclose(g);
    return 0;
}