Cod sursa(job #1950839)

Utilizator mateibanuBanu Matei Costin mateibanu Data 3 aprilie 2017 12:17:11
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

FILE*f=fopen("infasuratoare.in","r");
FILE*g=fopen("infasuratoare.out","w");

#define P 1e-12

int use[120002];

struct pct{
    double x,y;
    int p;
}v[120002],s[120002];

int cmp(pct a, pct b){
    return a.y<b.y||((a.y-b.y<=P&&b.y-a.y<=P)&&a.x<b.x);
}

int verif(double x1, double y1, double x2, double y2,int k){
    double a,b,c,p=1;
    b=1;
    if (x1-x2>P) {
        a=(y2-y1)/(x1-x2);
        c=-a*x1-b*y1;
        if (x1>x2) p=-1;
        if (a*v[k].x+b*v[k].y+c<=0)
            return -p;
        return p;
    }
    else {
        if (y1>y2) p=-1;
        if (v[k].x>x1||((v[k].x-x1<P&&x1-v[k].x<P))) return -p;
        else return p;
    }
}

int main()
{
    int n,i,nr;
    fscanf(f,"%d",&n);
    for (i=1;i<=n;i++){
        fscanf(f,"%lf%lf",&v[i].x,&v[i].y);v[i].p=i;}
    sort(v+1,v+n+1,cmp);
    s[1]=v[1];use[s[1].p]=1;
    s[2]=v[2];use[s[2].p]=1;
    nr=2;
    for (i=3;i<=n;i++){
        while (nr>=2&&verif(s[nr-1].x,s[nr-1].y,s[nr].x,s[nr].y,i)==-1){
            use[s[nr].p]=0;
            nr--;
        }
        nr++;
        s[nr]=v[i];
        use[s[nr].p]=1;
    }
    for (i=n;i>=1;i--)
        if (use[v[i].p]==0||i==1)
        {
        while (nr>=2&&verif(s[nr-1].x,s[nr-1].y,s[nr].x,s[nr].y,i)==-1){
            use[s[nr].p]=0;
            nr--;
        }
        nr++;
        s[nr]=v[i];
        use[s[nr].p]=1;
    }
    nr--;
    fprintf(g,"%d\n",nr);
    for (i=1;i<=nr;i++){
        fprintf(g,"%lf %lf\n",s[i].x,s[i].y);
    }
    fclose(f);
    fclose(g);
}